Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 超时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: