# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
28143 |
2017-07-15T13:09:18 Z |
zoomswk |
Teams (IOI15_teams) |
C++14 |
|
633 ms |
149684 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[]){
sort(K, K+M);
int cnt = 0;
stack<pair<int, int>> st; // {position used, remaining cnt}
for(int i=0; i<M; i++){
if(i == 0 || K[i] != K[i-1]){
int prev = 0;
if(i) prev = K[i-1];
// Remove ended students
cnt -= en_cnt[K[i]-1] - (prev > 0 ? en_cnt[prev-1] : 0);
while(!st.empty()){
int pos = st.top().first, rem = st.top().second;
st.pop();
int ok = qr(root[K[i]-1], pos, 1, N);
if(prev) ok -= qr(root[prev-1], pos, 1, N);
ok = min(ok, rem);
rem -= ok;
cnt += ok;
if(rem > 0){
st.push({pos, rem});
break;
}
}
// Add new students
cnt += st_cnt[K[i]]-st_cnt[prev];
}
// Finalize the business with this group
if(cnt < K[i]) return 0;
cnt -= K[i];
int topush = K[i];
while(!st.empty()){
if(st.top().first != K[i]) break;
topush += st.top().second;
st.pop();
}
st.push({K[i], topush});
}
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 |
3 ms |
136796 KB |
Output is correct |
2 |
Correct |
0 ms |
136796 KB |
Output is correct |
3 |
Correct |
0 ms |
136796 KB |
Output is correct |
4 |
Correct |
3 ms |
136796 KB |
Output is correct |
5 |
Correct |
3 ms |
136796 KB |
Output is correct |
6 |
Correct |
0 ms |
136796 KB |
Output is correct |
7 |
Correct |
0 ms |
136796 KB |
Output is correct |
8 |
Correct |
0 ms |
136796 KB |
Output is correct |
9 |
Correct |
6 ms |
136796 KB |
Output is correct |
10 |
Correct |
3 ms |
136796 KB |
Output is correct |
11 |
Correct |
9 ms |
136796 KB |
Output is correct |
12 |
Correct |
0 ms |
136796 KB |
Output is correct |
13 |
Incorrect |
3 ms |
136796 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
139428 KB |
Output is correct |
2 |
Correct |
86 ms |
139428 KB |
Output is correct |
3 |
Correct |
69 ms |
139428 KB |
Output is correct |
4 |
Correct |
73 ms |
139820 KB |
Output is correct |
5 |
Correct |
13 ms |
138240 KB |
Output is correct |
6 |
Correct |
13 ms |
138240 KB |
Output is correct |
7 |
Correct |
16 ms |
138240 KB |
Output is correct |
8 |
Correct |
39 ms |
138240 KB |
Output is correct |
9 |
Correct |
19 ms |
138432 KB |
Output is correct |
10 |
Correct |
16 ms |
138432 KB |
Output is correct |
11 |
Correct |
9 ms |
138432 KB |
Output is correct |
12 |
Correct |
19 ms |
138432 KB |
Output is correct |
13 |
Correct |
33 ms |
138500 KB |
Output is correct |
14 |
Correct |
43 ms |
139188 KB |
Output is correct |
15 |
Correct |
69 ms |
139296 KB |
Output is correct |
16 |
Correct |
63 ms |
139296 KB |
Output is correct |
17 |
Correct |
16 ms |
138156 KB |
Output is correct |
18 |
Correct |
19 ms |
138128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
139824 KB |
Output is correct |
2 |
Correct |
103 ms |
139820 KB |
Output is correct |
3 |
Correct |
149 ms |
142504 KB |
Output is correct |
4 |
Correct |
96 ms |
139820 KB |
Output is correct |
5 |
Correct |
53 ms |
138636 KB |
Output is correct |
6 |
Correct |
59 ms |
138636 KB |
Output is correct |
7 |
Correct |
16 ms |
138636 KB |
Output is correct |
8 |
Correct |
39 ms |
138636 KB |
Output is correct |
9 |
Correct |
19 ms |
138432 KB |
Output is correct |
10 |
Correct |
29 ms |
138460 KB |
Output is correct |
11 |
Correct |
23 ms |
138440 KB |
Output is correct |
12 |
Correct |
46 ms |
138568 KB |
Output is correct |
13 |
Incorrect |
89 ms |
138768 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
633 ms |
149684 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |