#include "teams.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n;
vector<int> sweep[500005];
int rt[500005], lf[20 * 500005], rg[20 * 500005], sum[20 * 500005], sz;
void upd(int bf, int &nd, int cl, int cr, int v){
nd = ++ sz;
lf[nd] = lf[bf]; rg[nd] = rg[bf]; sum[nd] = sum[bf] + 1;
if(cl == cr) return;
if(v <= (cl + cr) / 2)
upd(lf[bf], lf[nd], cl, (cl + cr) / 2, v);
else
upd(rg[bf], rg[nd], (cl + cr) / 2 + 1, cr, v);
}
int que(int nd, int cl, int cr, int ql, int qr){
if(qr < cl || cr < ql || cl > cr) return 0;
if(ql <= cl && cr <= qr) return sum[nd];
return que(lf[nd], cl, (cl + cr) / 2, ql, qr) + que(rg[nd], (cl + cr) / 2 + 1, cr, ql, qr);
}
void init(int N, int A[], int B[]){
n = N;
for(int i = 0; i < n; i ++)
sweep[A[i]].push_back(B[i]);
for(int i = 1; i <= n; i ++){
rt[i] = rt[i - 1];
for(int x : sweep[i])
upd(rt[i], rt[i], 1, n, x);
}
}
int val[500005], cnt[500005], used[500005];
int can(int M, int K[]){
// (N + M) log N
// vector<int> cnt(n + 1, 0);
// for(int i = 0; i < M; i ++)
// cnt[K[i]] += K[i];
// priority_queue<int, vector<int>, greater<int> > pq;
// for(int i = 1; i <= n; i ++){
// for(int x : sweep[i]) pq.push(x);
// while(pq.size() && pq.top() < i) pq.pop();
// if(pq.size() < cnt[i]) return 0;
// for(; cnt[i] --; pq.pop());
// }
// return 1;
// M^2 log N
sort(K, K + M);
int sum = 0, id = 0;
for(int i = 0; i < M; i ++){
sum += K[i];
if(id > 0 && val[id - 1] == K[i])
cnt[id - 1] += K[i];
else
val[id] = cnt[id] = K[i], id ++;
}
val[id] = n + 1;
if(sum > n) return 0;
for(int i = 0; i < id; i ++)
used[i] = 0;
for(int i = 0; i < id; i ++){
int need = cnt[i];
for(int j = i; j < id; j ++){
int have = que(rt[val[i]], 1, n, val[j], val[j + 1] - 1) - used[j];
int add = min(have, need);
need -= add; used[j] += add;
if(need <= 0) break;
}
if(need > 0) return 0;
}
return 1;
}
Compilation message
teams.cpp: In function 'int can(int, int*)':
teams.cpp:59:6: warning: declaration of 'sum' shadows a global declaration [-Wshadow]
59 | int sum = 0, id = 0;
| ^~~
teams.cpp:10:51: note: shadowed declaration is here
10 | int rt[500005], lf[20 * 500005], rg[20 * 500005], sum[20 * 500005], sz;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12160 KB |
Output is correct |
2 |
Correct |
9 ms |
12040 KB |
Output is correct |
3 |
Correct |
8 ms |
12160 KB |
Output is correct |
4 |
Correct |
8 ms |
12160 KB |
Output is correct |
5 |
Correct |
8 ms |
12160 KB |
Output is correct |
6 |
Correct |
9 ms |
12160 KB |
Output is correct |
7 |
Correct |
8 ms |
12160 KB |
Output is correct |
8 |
Correct |
8 ms |
12160 KB |
Output is correct |
9 |
Correct |
8 ms |
12160 KB |
Output is correct |
10 |
Correct |
8 ms |
12160 KB |
Output is correct |
11 |
Correct |
8 ms |
12160 KB |
Output is correct |
12 |
Correct |
8 ms |
12160 KB |
Output is correct |
13 |
Correct |
9 ms |
12160 KB |
Output is correct |
14 |
Correct |
9 ms |
12160 KB |
Output is correct |
15 |
Correct |
8 ms |
12160 KB |
Output is correct |
16 |
Correct |
8 ms |
12160 KB |
Output is correct |
17 |
Correct |
8 ms |
12160 KB |
Output is correct |
18 |
Correct |
9 ms |
12160 KB |
Output is correct |
19 |
Correct |
8 ms |
12160 KB |
Output is correct |
20 |
Correct |
8 ms |
12160 KB |
Output is correct |
21 |
Correct |
8 ms |
12160 KB |
Output is correct |
22 |
Correct |
8 ms |
12160 KB |
Output is correct |
23 |
Correct |
9 ms |
12156 KB |
Output is correct |
24 |
Correct |
8 ms |
12160 KB |
Output is correct |
25 |
Correct |
8 ms |
12160 KB |
Output is correct |
26 |
Correct |
9 ms |
12160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
36984 KB |
Output is correct |
2 |
Correct |
67 ms |
36984 KB |
Output is correct |
3 |
Correct |
65 ms |
36984 KB |
Output is correct |
4 |
Correct |
68 ms |
37624 KB |
Output is correct |
5 |
Correct |
44 ms |
35448 KB |
Output is correct |
6 |
Correct |
41 ms |
35452 KB |
Output is correct |
7 |
Correct |
40 ms |
35448 KB |
Output is correct |
8 |
Correct |
40 ms |
35448 KB |
Output is correct |
9 |
Correct |
40 ms |
34544 KB |
Output is correct |
10 |
Correct |
39 ms |
34288 KB |
Output is correct |
11 |
Correct |
41 ms |
35568 KB |
Output is correct |
12 |
Correct |
40 ms |
34416 KB |
Output is correct |
13 |
Correct |
47 ms |
36084 KB |
Output is correct |
14 |
Correct |
50 ms |
35568 KB |
Output is correct |
15 |
Correct |
62 ms |
36856 KB |
Output is correct |
16 |
Correct |
62 ms |
36856 KB |
Output is correct |
17 |
Correct |
44 ms |
36216 KB |
Output is correct |
18 |
Correct |
44 ms |
36088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
116 ms |
37752 KB |
Output is correct |
2 |
Correct |
125 ms |
37752 KB |
Output is correct |
3 |
Correct |
176 ms |
41080 KB |
Output is correct |
4 |
Correct |
70 ms |
37616 KB |
Output is correct |
5 |
Correct |
65 ms |
36216 KB |
Output is correct |
6 |
Correct |
66 ms |
36304 KB |
Output is correct |
7 |
Correct |
61 ms |
36216 KB |
Output is correct |
8 |
Correct |
70 ms |
36216 KB |
Output is correct |
9 |
Correct |
43 ms |
34672 KB |
Output is correct |
10 |
Correct |
41 ms |
34772 KB |
Output is correct |
11 |
Correct |
82 ms |
36080 KB |
Output is correct |
12 |
Correct |
1317 ms |
35184 KB |
Output is correct |
13 |
Correct |
331 ms |
37108 KB |
Output is correct |
14 |
Correct |
209 ms |
39160 KB |
Output is correct |
15 |
Correct |
95 ms |
37628 KB |
Output is correct |
16 |
Correct |
93 ms |
37712 KB |
Output is correct |
17 |
Correct |
69 ms |
36856 KB |
Output is correct |
18 |
Correct |
69 ms |
36700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
606 ms |
147064 KB |
Output is correct |
2 |
Correct |
592 ms |
152424 KB |
Output is correct |
3 |
Correct |
762 ms |
159096 KB |
Output is correct |
4 |
Correct |
461 ms |
151928 KB |
Output is correct |
5 |
Correct |
247 ms |
143480 KB |
Output is correct |
6 |
Correct |
248 ms |
143448 KB |
Output is correct |
7 |
Correct |
225 ms |
143352 KB |
Output is correct |
8 |
Correct |
244 ms |
143480 KB |
Output is correct |
9 |
Correct |
186 ms |
136808 KB |
Output is correct |
10 |
Correct |
186 ms |
141032 KB |
Output is correct |
11 |
Correct |
2128 ms |
142056 KB |
Output is correct |
12 |
Execution timed out |
4073 ms |
143044 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |