Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

为什么跑了3000多ms,求大神优化

Posted by skt at 2013-07-15 16:40:04 on Problem 2828
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <iostream>
#define LL long long
#define Eps 1e-8
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
#define LS(x) x<<1
#define RS(x) x<<1|1
#define Mid(a,b) (a+b)>>1
#define MAXN 200005
using namespace std;
const int inf = 0x13131313;
int n,cost;
int Pos[MAXN] = {0}, Val[MAXN] = {0};
int Value[MAXN];
int Count[MAXN << 2];
void pushup(int pos) {
	Count[pos] = Count[LS(pos)] + Count[RS(pos)];
}
void build(int l,int r,int pos) 
{
	Count[pos] = 1; //记录空格的个数
	if(l == r) {
		return ;
	}
	int m = Mid(l,r);	
	build(l,m,LS(pos));
	build(m+1,r,RS(pos));
	pushup(pos);
}
//统计空格的个数,通过空格来获得下标
void Query(int pos,int l,int r,int num) {
	if(l == r) {
		if(Count[pos] == num) {
			Value[r] = cost,Count[pos] = 0;
			return ;
		}
	}
	int m = Mid(l,r);
	int ls = Count[LS(pos)];
	if(num > ls)
		Query(RS(pos) , m+1 , r, num - ls);
	else
		Query(LS(pos) , l , m, num);
	pushup(pos);
}
void work()
{
	build(1,n,1);
	for(int i = 0; i < n; i ++)
		scanf("%d %d",&Pos[i],&Val[i]);
	for(int i = n-1; i >= 0; i --) {
		int num = Pos[i]+1;
		cost = Val[i];
		Query(1,1,n,num);
	}
	for(int i = 1; i <= n-1; i ++)
		printf("%d ",Value[i]);
	printf("%d\n",Value[n]);
}
int main()
{
	while(scanf("%d",&n) != EOF)
		work();
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator