| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 43615 |
2018-03-18T08:19:06 Z |
szawinis |
Teams (IOI15_teams) |
C++14 |
|
2309 ms |
357936 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5+10;
int n, used_root, root[N];
vector<int> ls[N], t, nxtl, nxtr;
int newLeaf(int v) {
t.push_back(v);
nxtl.push_back(-1);
nxtr.push_back(-1);
return t.size()-1;
}
int newPar(int l, int r) {
t.push_back(t[l] + t[r]);
nxtl.push_back(l);
nxtr.push_back(r);
return t.size()-1;
}
int build(int l = 0, int r = N-1) {
if(l == r) return newLeaf(0);
int mid = l+r >> 1;
return newPar(build(l, mid), build(mid+1, r));
}
int update(int i, int targ, int l = 0, int r = N-1) {
if(l == r) return newLeaf(t[i] + 1);
int mid = l+r >> 1;
if(targ <= mid) return newPar(update(nxtl[i], targ, l, mid), nxtr[i]);
else return newPar(nxtl[i], update(nxtr[i], targ, mid+1, r));
}
int erase(int i, int zeroi, int targ, int l = 0, int r = N-1) {
if(r <= targ) return zeroi;
if(l > targ) return i;
int mid = l+r >> 1;
return newPar(erase(nxtl[i], nxtl[zeroi], targ, l, mid), erase(nxtr[i], nxtr[zeroi], targ, mid+1, r));
}
int query(int avail, int used, int k, int l = 0, int r = N-1) {// returns index of new used root, but -1 if failure
if(t[avail] - t[used] < k) return -1;
if(l == r) return newLeaf(t[used] + k);
int cntl = t[nxtl[avail]] - t[nxtl[used]];
int mid = l+r >> 1;
if(cntl >= k)
return newPar(query(nxtl[avail], nxtl[used], k, l, mid), nxtr[used]);
else
return newPar(nxtl[avail], query(nxtr[avail], nxtr[used], k - cntl, mid+1, r));
}
int get(int i, int tl, int tr, int l = 0, int r = N-1) {
if(r < tl || l > tr) return 0;
if(l >= tl && r <= tr) return t[i];
int mid = l+r >> 1, ret = 0;
if(nxtl[i] != -1) ret += get(nxtl[i], tl, tr, l, mid);
if(nxtr[i] != -1) ret += get(nxtr[i], tl, tr, mid+1, r);
return ret;
}
void init(int _n, int a[], int b[]) {
n = _n;
for(int i = 0; i < n; i++) ls[a[i]].push_back(b[i]);
root[0] = build();
for(int i = 1; i <= n; i++) { // direction of iteration is insignificant
root[i] = erase(root[i-1], root[0], i-1);
for(int j = 0; j < ls[i].size(); j++) root[i] = update(root[i], ls[i][j]);
}
used_root = build();
}
int can(int m, int k[]) {
sort(k, k+m);
int used = used_root;
for(int i = 0; i < m; i++) {
used = erase(used, root[0], k[i]-1);
used = query(root[k[i]], used, k[i]);
if(used == -1) return 0;
}
return 1;
}
Compilation message
teams.cpp: In function 'int newLeaf(int)':
teams.cpp:13:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
return t.size()-1;
^
teams.cpp: In function 'int newPar(int, int)':
teams.cpp:19:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
return t.size()-1;
^
teams.cpp: In function 'int build(int, int)':
teams.cpp:23:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l+r >> 1;
^
teams.cpp: In function 'int update(int, int, int, int)':
teams.cpp:28:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l+r >> 1;
^
teams.cpp: In function 'int erase(int, int, int, int, int)':
teams.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l+r >> 1;
^
teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l+r >> 1;
^
teams.cpp: In function 'int get(int, int, int, int, int)':
teams.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l+r >> 1, ret = 0;
^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < ls[i].size(); j++) root[i] = update(root[i], ls[i][j]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
35608 KB |
Output is correct |
| 2 |
Correct |
58 ms |
35704 KB |
Output is correct |
| 3 |
Correct |
59 ms |
35936 KB |
Output is correct |
| 4 |
Correct |
59 ms |
35936 KB |
Output is correct |
| 5 |
Correct |
61 ms |
35936 KB |
Output is correct |
| 6 |
Correct |
72 ms |
35964 KB |
Output is correct |
| 7 |
Correct |
58 ms |
36520 KB |
Output is correct |
| 8 |
Correct |
58 ms |
36520 KB |
Output is correct |
| 9 |
Correct |
58 ms |
36520 KB |
Output is correct |
| 10 |
Correct |
66 ms |
36520 KB |
Output is correct |
| 11 |
Correct |
58 ms |
36520 KB |
Output is correct |
| 12 |
Correct |
95 ms |
45332 KB |
Output is correct |
| 13 |
Correct |
65 ms |
45332 KB |
Output is correct |
| 14 |
Correct |
61 ms |
45332 KB |
Output is correct |
| 15 |
Correct |
57 ms |
45332 KB |
Output is correct |
| 16 |
Correct |
58 ms |
45332 KB |
Output is correct |
| 17 |
Correct |
66 ms |
45332 KB |
Output is correct |
| 18 |
Correct |
63 ms |
45332 KB |
Output is correct |
| 19 |
Correct |
63 ms |
45332 KB |
Output is correct |
| 20 |
Correct |
61 ms |
45332 KB |
Output is correct |
| 21 |
Correct |
71 ms |
45332 KB |
Output is correct |
| 22 |
Correct |
61 ms |
45332 KB |
Output is correct |
| 23 |
Correct |
78 ms |
45332 KB |
Output is correct |
| 24 |
Correct |
59 ms |
45332 KB |
Output is correct |
| 25 |
Correct |
61 ms |
45332 KB |
Output is correct |
| 26 |
Correct |
59 ms |
45332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
297 ms |
83808 KB |
Output is correct |
| 2 |
Correct |
296 ms |
83808 KB |
Output is correct |
| 3 |
Correct |
286 ms |
83916 KB |
Output is correct |
| 4 |
Correct |
310 ms |
83916 KB |
Output is correct |
| 5 |
Correct |
212 ms |
83916 KB |
Output is correct |
| 6 |
Correct |
209 ms |
83916 KB |
Output is correct |
| 7 |
Correct |
198 ms |
83916 KB |
Output is correct |
| 8 |
Correct |
200 ms |
83916 KB |
Output is correct |
| 9 |
Correct |
219 ms |
97380 KB |
Output is correct |
| 10 |
Correct |
213 ms |
97380 KB |
Output is correct |
| 11 |
Correct |
199 ms |
97380 KB |
Output is correct |
| 12 |
Correct |
235 ms |
97380 KB |
Output is correct |
| 13 |
Correct |
219 ms |
97380 KB |
Output is correct |
| 14 |
Correct |
239 ms |
97380 KB |
Output is correct |
| 15 |
Correct |
269 ms |
97380 KB |
Output is correct |
| 16 |
Correct |
276 ms |
97380 KB |
Output is correct |
| 17 |
Correct |
208 ms |
97380 KB |
Output is correct |
| 18 |
Correct |
212 ms |
97380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
296 ms |
97380 KB |
Output is correct |
| 2 |
Correct |
298 ms |
97380 KB |
Output is correct |
| 3 |
Correct |
626 ms |
150160 KB |
Output is correct |
| 4 |
Correct |
311 ms |
150160 KB |
Output is correct |
| 5 |
Correct |
398 ms |
150160 KB |
Output is correct |
| 6 |
Correct |
383 ms |
150160 KB |
Output is correct |
| 7 |
Correct |
210 ms |
150160 KB |
Output is correct |
| 8 |
Correct |
280 ms |
150160 KB |
Output is correct |
| 9 |
Correct |
252 ms |
150160 KB |
Output is correct |
| 10 |
Correct |
372 ms |
150160 KB |
Output is correct |
| 11 |
Correct |
375 ms |
150160 KB |
Output is correct |
| 12 |
Correct |
407 ms |
150160 KB |
Output is correct |
| 13 |
Correct |
542 ms |
150160 KB |
Output is correct |
| 14 |
Correct |
685 ms |
150160 KB |
Output is correct |
| 15 |
Correct |
468 ms |
150160 KB |
Output is correct |
| 16 |
Correct |
452 ms |
150160 KB |
Output is correct |
| 17 |
Correct |
362 ms |
150160 KB |
Output is correct |
| 18 |
Correct |
356 ms |
150160 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1563 ms |
290060 KB |
Output is correct |
| 2 |
Correct |
1569 ms |
290060 KB |
Output is correct |
| 3 |
Correct |
2169 ms |
345960 KB |
Output is correct |
| 4 |
Correct |
1498 ms |
345960 KB |
Output is correct |
| 5 |
Correct |
1012 ms |
357432 KB |
Output is correct |
| 6 |
Correct |
963 ms |
357432 KB |
Output is correct |
| 7 |
Correct |
831 ms |
357432 KB |
Output is correct |
| 8 |
Correct |
935 ms |
357432 KB |
Output is correct |
| 9 |
Correct |
936 ms |
357432 KB |
Output is correct |
| 10 |
Correct |
986 ms |
357432 KB |
Output is correct |
| 11 |
Correct |
985 ms |
357432 KB |
Output is correct |
| 12 |
Correct |
1096 ms |
357488 KB |
Output is correct |
| 13 |
Correct |
1462 ms |
357936 KB |
Output is correct |
| 14 |
Correct |
2309 ms |
357936 KB |
Output is correct |
| 15 |
Correct |
1383 ms |
357936 KB |
Output is correct |
| 16 |
Correct |
1399 ms |
357936 KB |
Output is correct |
| 17 |
Correct |
958 ms |
357936 KB |
Output is correct |
| 18 |
Correct |
963 ms |
357936 KB |
Output is correct |
