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

+1

Posted by ysymi at 2013-02-17 20:46:22 on Problem 2828
In Reply To:同样的code, c++1625MS, g++3625ms Posted by:jerryjiang at 2011-06-25 13:41:02
> 没用stl,请问怎么回事? 谢了!
> 
> #include <iostream>
> #include <cstdio>
> #include <cstdlib>
> #include <cstring>
> #include <vector>
> #include <list>
> #include <map>
> #include <set>
> #include <stack>
> #include <queue>
> #include <deque>
> #include <string>
> #include <cmath>
> #include <iomanip>
> #include <limits>
> #include <algorithm>
> #include <ctime>
> using namespace std;
> 
> const int MAXN = 200001;
> 
> int post[MAXN];
> int value[MAXN];
> 
> struct Node {
> 	Node() : value(-1){};
> 	int left, right, num, value;
> };
> 
> Node array[3 * MAXN];
> 
> int result[MAXN];
> 
> void BuildTree(int v, int l, int r) {
> 	array[v].left = l;
> 	array[v].right = r;
> 	array[v].num = r - l + 1;
> 	array[v].value = -1;
> 
> 	if (l >= r) return;
> 
> 	int mid = (l + r) / 2;
> 
> 	BuildTree(2 * v, l , mid);
> 	BuildTree(2 * v + 1, mid + 1, r);
> }
> 
> void Insert(int v, int i, int pos)
> {
> 	array[v].num--;
> 
> 	if (array[v].left == array[v].right) {
> 		array[v].value = value[i];
> 		result[array[v].left] = value[i];
> 		return;
> 	}
> 
> 	if (array[2 * v].num > pos) {
> 		Insert(2 * v, i, pos);
> 	} else {
> 		Insert(2 * v + 1, i, pos - array[2 * v].num);
> 	}
> }
> 
> int main() {
> //	freopen("input","r",stdin);
> 
> 	int N;
> 	while (cin >> N) {
> 		for (int i = 1; i <= N; i++) {
> 			scanf("%d %d", &post[i], &value[i]);
> 		}
> 
> 		BuildTree(1, 1, N);
> 
> 		for (int i = N; i >= 1; i--) {
> 			Insert(1, i, post[i]);
> 		}
> 
> 		for (int i = 1; i <= N; i++) {
> 			if (i != N) {
> 				printf("%d ", result[i]);
> 			} else {
> 				printf("%d", result[i]);
> 			}
> 		}
> 		printf("%c", '\n');
> 
> 	}
> 	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