# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
28160 |
2017-07-15T13:55:18 Z |
zoomswk |
Teams (IOI15_teams) |
C++14 |
|
1493 ms |
149680 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 500005;
int T[MAX_N*20], L[MAX_N*20], R[MAX_N*20];
int root[MAX_N];
int nodecnt=2;
int N;
void build(int node, int l, int r){
if(l == r) return;
L[node] = nodecnt++;
R[node] = nodecnt++;
int mid = (l+r)>>1;
build(L[node], l, mid);
build(R[node], mid+1, r);
return;
}
void upd(int prev, int node, int l, int r, int pos){
if(l == r){
T[node] = T[prev]+1;
return;
}
int mid = (l+r)>>1;
L[node] = L[prev], R[node] = R[prev];
if(pos <= mid){
L[node] = nodecnt++;
upd(L[prev], L[node], l, mid, pos);
} else{
R[node] = nodecnt++;
upd(R[prev], R[node], mid+1, r, pos);
}
T[node] = T[L[node]] + T[R[node]];
return;
}
int qr(int node, int until, int cur_l, int cur_r){
if(cur_r <= until) return T[node];
if(cur_l > until) return 0;
int mid = (cur_l+cur_r)>>1;
return qr(L[node], until, cur_l, mid) + qr(R[node], until, mid+1, cur_r);
}
vector<int> r[500005];
int st_cnt[500005], en_cnt[500005];
void init(int n, int A[], int B[]){
N = n;
for(int i=0; i<N; i++) r[B[i]].push_back(A[i]), st_cnt[A[i]]++, en_cnt[B[i]]++;
for(int i=1; i<=N; i++) st_cnt[i] += st_cnt[i-1], en_cnt[i] += en_cnt[i-1];
root[0] = 1;
build(1, 1, N);
for(int i=1; i<=N; i++){
root[i] = root[i-1];
if(r[i].size()){
int prev = root[i-1];
root[i] = nodecnt++;
upd(prev, root[i], 1, N, r[i][0]);
for(int j=1; j<r[i].size(); j++){
int prev = root[i];
root[i] = nodecnt++;
upd(prev, root[i], 1, N, r[i][j]);
}
}
}
return;
}
int can(int M, int K[]){
long long sum = 0;
for(int i=0; i<M; i++) sum += K[i];
if(sum > N) return 0;
sort(K, K+M);
int A[M], CNT[M];
int ptr = 0;
for(int i=0; i<M; i++) A[i] = 0, CNT[i] = 0;
for(int i=0; i<M; i++){
if(i == 0 || K[i] != K[i-1]){
A[ptr] = K[i];
CNT[ptr++] = K[i];
} else{
CNT[ptr-1] += K[i];
}
}
int cnt = 0;
for(int i=0; i<ptr; i++){
int prev = 0;
if(i) prev = A[i-1];
// remove done students
cnt -= en_cnt[A[i]-1] - (prev > 0 ? en_cnt[prev-1] : 0);
int done = 0;
for(int j=0; j<i; j++){
if(!CNT[j]) continue;
int ok = qr(root[A[i]-1], A[j], 1, N);
ok -= qr(root[prev-1], A[j], 1, N);
ok = min(ok-done, CNT[j]);
CNT[j] -= ok;
cnt += ok;
done += ok;
}
// add new students
cnt += st_cnt[A[i]] - st_cnt[prev];
if(cnt < CNT[i]) return 0;
cnt -= CNT[i];
}
return 1;
}
Compilation message
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:62:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=1; j<r[i].size(); j++){
^
teams.cpp:63:21: warning: declaration of 'prev' shadows a previous local [-Wshadow]
int prev = root[i];
^
teams.cpp:59:17: note: shadowed declaration is here
int prev = root[i-1];
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
136792 KB |
Output is correct |
2 |
Correct |
0 ms |
136792 KB |
Output is correct |
3 |
Correct |
0 ms |
136792 KB |
Output is correct |
4 |
Correct |
9 ms |
136792 KB |
Output is correct |
5 |
Correct |
0 ms |
136792 KB |
Output is correct |
6 |
Correct |
6 ms |
136792 KB |
Output is correct |
7 |
Correct |
6 ms |
136792 KB |
Output is correct |
8 |
Correct |
0 ms |
136792 KB |
Output is correct |
9 |
Correct |
0 ms |
136792 KB |
Output is correct |
10 |
Correct |
0 ms |
136792 KB |
Output is correct |
11 |
Correct |
0 ms |
136792 KB |
Output is correct |
12 |
Correct |
0 ms |
136792 KB |
Output is correct |
13 |
Correct |
6 ms |
136792 KB |
Output is correct |
14 |
Correct |
0 ms |
136792 KB |
Output is correct |
15 |
Correct |
3 ms |
136792 KB |
Output is correct |
16 |
Correct |
0 ms |
136792 KB |
Output is correct |
17 |
Correct |
3 ms |
136792 KB |
Output is correct |
18 |
Correct |
0 ms |
136792 KB |
Output is correct |
19 |
Correct |
0 ms |
136792 KB |
Output is correct |
20 |
Correct |
3 ms |
136792 KB |
Output is correct |
21 |
Correct |
3 ms |
136792 KB |
Output is correct |
22 |
Correct |
3 ms |
136792 KB |
Output is correct |
23 |
Correct |
6 ms |
136792 KB |
Output is correct |
24 |
Correct |
6 ms |
136792 KB |
Output is correct |
25 |
Correct |
0 ms |
136792 KB |
Output is correct |
26 |
Correct |
3 ms |
136792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
139424 KB |
Output is correct |
2 |
Correct |
79 ms |
139424 KB |
Output is correct |
3 |
Correct |
96 ms |
139424 KB |
Output is correct |
4 |
Correct |
73 ms |
140472 KB |
Output is correct |
5 |
Correct |
19 ms |
138236 KB |
Output is correct |
6 |
Correct |
19 ms |
138236 KB |
Output is correct |
7 |
Correct |
19 ms |
138236 KB |
Output is correct |
8 |
Correct |
23 ms |
138236 KB |
Output is correct |
9 |
Correct |
16 ms |
138432 KB |
Output is correct |
10 |
Correct |
16 ms |
138428 KB |
Output is correct |
11 |
Correct |
9 ms |
138428 KB |
Output is correct |
12 |
Correct |
16 ms |
138428 KB |
Output is correct |
13 |
Correct |
33 ms |
138496 KB |
Output is correct |
14 |
Correct |
49 ms |
139184 KB |
Output is correct |
15 |
Correct |
89 ms |
139292 KB |
Output is correct |
16 |
Correct |
96 ms |
139292 KB |
Output is correct |
17 |
Correct |
33 ms |
138152 KB |
Output is correct |
18 |
Correct |
29 ms |
138124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
139820 KB |
Output is correct |
2 |
Correct |
89 ms |
139820 KB |
Output is correct |
3 |
Correct |
133 ms |
142460 KB |
Output is correct |
4 |
Correct |
96 ms |
140472 KB |
Output is correct |
5 |
Correct |
96 ms |
138632 KB |
Output is correct |
6 |
Correct |
69 ms |
138632 KB |
Output is correct |
7 |
Correct |
19 ms |
138632 KB |
Output is correct |
8 |
Correct |
49 ms |
138632 KB |
Output is correct |
9 |
Correct |
16 ms |
138436 KB |
Output is correct |
10 |
Correct |
19 ms |
138476 KB |
Output is correct |
11 |
Correct |
76 ms |
138436 KB |
Output is correct |
12 |
Correct |
1493 ms |
138564 KB |
Output is correct |
13 |
Correct |
179 ms |
138764 KB |
Output is correct |
14 |
Correct |
119 ms |
141016 KB |
Output is correct |
15 |
Correct |
83 ms |
139688 KB |
Output is correct |
16 |
Correct |
106 ms |
139688 KB |
Output is correct |
17 |
Correct |
43 ms |
138572 KB |
Output is correct |
18 |
Correct |
56 ms |
138560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
589 ms |
149680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |