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

超时TLE!怎么办?

Posted by hutianxiang at 2016-06-11 13:51:45 on Problem 2481
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 100100

int n, c[MAXN];

struct node {
	int id, s, e, pos, ans;
}d[MAXN];

bool cmp1(node x, node y) {
	return x.s < y.s;
}

bool cmp2(node x, node y) {
	if (x.e == y.e) return x.s < y.s;
	else return x.e > y.e;
}

bool cmp3(node x, node y) {
	return x.pos < y.pos;
}

int lowbit(int x) {
	return x&(x ^ (x - 1));
}

void change(int i, int data) {
	c[i] += data;
	for (; i <= n; i += lowbit(i)) c[i] += data;
}

int sum(int i) {
	int s = 0;
	for (; i; i -= lowbit(i)) s += c[i];
	return s;
}

int main() {
	while (scanf("%d", &n) != EOF) {
		if (n == 0) break;
		memset(d, 0, sizeof(d));
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &d[i].s, &d[i].e);
			d[i].s++, d[i].e++;
			d[i].pos = i;
		}
		sort(d + 1, d + n + 1, cmp1);
		int cnt = 1;
		d[1].id = cnt;
		for (int i = 2; i <= n; i++) {
			if (d[i].s == d[i - 1].s) d[i].id = cnt;
			else d[i].id = ++cnt;
		}
		sort(d + 1, d + n + 1, cmp2);

		for (int i = 1; i <= n; i++) {
			if (i > 1) {
				if (d[i].s == d[i - 1].s && d[i].e == d[i - 1].e) d[i].ans = d[i - 1].ans;
				else d[i].ans = sum(d[i].id);
			}
			change(d[i].id, 1);
		}
		sort(d + 1, d + n + 1, cmp3);

		for (int i = 1; i <= n; i++) printf("%d ", d[i].ans);
		printf("\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