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大学生程序设计竞赛训练》暑期课面向全球招生!

同样的code, c++1625MS, g++3625ms

Posted by jerryjiang at 2011-06-25 13:41:02 on Problem 2828
没用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