# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
887033 | 2023-12-13T13:57:46 Z | abcvuitunggio | Teams (IOI15_teams) | C++17 | 1238 ms | 338072 KB |
#include "teams.h" #include <bits/stdc++.h> using namespace std; const int INF=1e9; int n,cnt[500001],dp[1010],root[500001],st[40000001],le[40000001],ri[40000001],nNode,nRoot,R[500001],pos[500001]; vector <int> v[500001],ve,tmp; int update(int node, int l, int r, int u, int v){ int mid=(l+r)>>1,cur=++nNode; st[cur]=st[node]; le[cur]=le[node]; ri[cur]=ri[node]; if (l>=u&&r<=v){ st[cur]++; return cur; } if (u<=mid) le[cur]=update(le[node],l,mid,u,v); if (v>mid) ri[cur]=update(ri[node],mid+1,r,u,v); return cur; } void fakeget(int l=1, int r=n, int u=1, int v=ve.size()-1){ if (u>v||ve[v]<l||ve[u]>r) return; if (l==r) return; int mid=(l+r)>>1; pos[mid]=upper_bound(ve.begin(),ve.end(),mid)-ve.begin(); fakeget(l,mid,u,min(v,pos[mid]-1)); fakeget(mid+1,r,max(pos[mid],u),v); } int get(int node, int l, int r, int u, int v){ if (u>v||ve[v]<l||ve[u]>r) return -INF; if (l==r) return dp[u]-st[node]; int mid=(l+r)>>1; return max(get(le[node],l,mid,u,min(v,pos[mid]-1)),get(ri[node],mid+1,r,max(pos[mid],u),v))-st[node]; } void init(int N, int A[], int B[]){ n=N; for (int i=0;i<n;i++) v[A[i]].push_back(B[i]); for (int i=n;i;i--){ for (int j:v[i]){ nRoot++; root[nRoot]=update(root[nRoot-1],1,n,i,j); } R[i]=root[nRoot]; } } int can(int M, int K[]){ int sum=0; for (int i=0;i<M;i++){ sum+=K[i]; cnt[K[i]]=0; if (sum>n) return 0; } ve={0}; for (int i=0;i<M;i++){ if (!cnt[K[i]]) ve.push_back(K[i]); cnt[K[i]]+=K[i]; } sort(ve.begin(),ve.end()); fakeget(); for (int i=ve.size()-1;i>=0;i--) dp[i]=max(get(R[ve[i]+1],1,n,i+1,ve.size()-1),0)+cnt[ve[i]]; return (!dp[0]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 16988 KB | Output is correct |
2 | Correct | 3 ms | 16988 KB | Output is correct |
3 | Correct | 3 ms | 16988 KB | Output is correct |
4 | Correct | 3 ms | 16988 KB | Output is correct |
5 | Correct | 3 ms | 16988 KB | Output is correct |
6 | Correct | 3 ms | 16988 KB | Output is correct |
7 | Correct | 3 ms | 16988 KB | Output is correct |
8 | Correct | 3 ms | 16988 KB | Output is correct |
9 | Correct | 4 ms | 16984 KB | Output is correct |
10 | Correct | 3 ms | 17240 KB | Output is correct |
11 | Correct | 3 ms | 16988 KB | Output is correct |
12 | Correct | 3 ms | 17004 KB | Output is correct |
13 | Correct | 3 ms | 16988 KB | Output is correct |
14 | Correct | 3 ms | 16988 KB | Output is correct |
15 | Correct | 3 ms | 16984 KB | Output is correct |
16 | Correct | 3 ms | 16988 KB | Output is correct |
17 | Correct | 3 ms | 16984 KB | Output is correct |
18 | Correct | 3 ms | 16988 KB | Output is correct |
19 | Correct | 3 ms | 16988 KB | Output is correct |
20 | Correct | 4 ms | 16988 KB | Output is correct |
21 | Correct | 3 ms | 16988 KB | Output is correct |
22 | Correct | 4 ms | 16988 KB | Output is correct |
23 | Correct | 3 ms | 16984 KB | Output is correct |
24 | Correct | 4 ms | 16988 KB | Output is correct |
25 | Correct | 4 ms | 16988 KB | Output is correct |
26 | Correct | 3 ms | 16988 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 59 ms | 74324 KB | Output is correct |
2 | Correct | 60 ms | 74180 KB | Output is correct |
3 | Correct | 57 ms | 74280 KB | Output is correct |
4 | Correct | 58 ms | 74576 KB | Output is correct |
5 | Correct | 21 ms | 42456 KB | Output is correct |
6 | Correct | 21 ms | 42332 KB | Output is correct |
7 | Correct | 21 ms | 42328 KB | Output is correct |
8 | Correct | 22 ms | 42332 KB | Output is correct |
9 | Correct | 11 ms | 21716 KB | Output is correct |
10 | Correct | 19 ms | 42196 KB | Output is correct |
11 | Correct | 21 ms | 42196 KB | Output is correct |
12 | Correct | 22 ms | 46260 KB | Output is correct |
13 | Correct | 36 ms | 62804 KB | Output is correct |
14 | Correct | 34 ms | 42708 KB | Output is correct |
15 | Correct | 58 ms | 72028 KB | Output is correct |
16 | Correct | 55 ms | 72028 KB | Output is correct |
17 | Correct | 26 ms | 50524 KB | Output is correct |
18 | Correct | 33 ms | 62776 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 265 ms | 74836 KB | Output is correct |
2 | Correct | 266 ms | 74724 KB | Output is correct |
3 | Correct | 133 ms | 77580 KB | Output is correct |
4 | Correct | 64 ms | 74600 KB | Output is correct |
5 | Correct | 227 ms | 42812 KB | Output is correct |
6 | Correct | 224 ms | 42852 KB | Output is correct |
7 | Correct | 221 ms | 42764 KB | Output is correct |
8 | Correct | 261 ms | 42976 KB | Output is correct |
9 | Correct | 9 ms | 21712 KB | Output is correct |
10 | Correct | 19 ms | 42452 KB | Output is correct |
11 | Correct | 24 ms | 42452 KB | Output is correct |
12 | Correct | 197 ms | 46640 KB | Output is correct |
13 | Correct | 169 ms | 63476 KB | Output is correct |
14 | Correct | 157 ms | 71764 KB | Output is correct |
15 | Correct | 101 ms | 72448 KB | Output is correct |
16 | Correct | 101 ms | 72448 KB | Output is correct |
17 | Correct | 82 ms | 55408 KB | Output is correct |
18 | Correct | 80 ms | 73424 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1238 ms | 331776 KB | Output is correct |
2 | Correct | 1234 ms | 331480 KB | Output is correct |
3 | Correct | 656 ms | 338072 KB | Output is correct |
4 | Correct | 438 ms | 331428 KB | Output is correct |
5 | Correct | 952 ms | 147572 KB | Output is correct |
6 | Correct | 954 ms | 147024 KB | Output is correct |
7 | Correct | 957 ms | 147044 KB | Output is correct |
8 | Correct | 959 ms | 147100 KB | Output is correct |
9 | Correct | 29 ms | 34816 KB | Output is correct |
10 | Correct | 97 ms | 164296 KB | Output is correct |
11 | Correct | 202 ms | 164304 KB | Output is correct |
12 | Correct | 785 ms | 189496 KB | Output is correct |
13 | Correct | 770 ms | 266848 KB | Output is correct |
14 | Correct | 741 ms | 309532 KB | Output is correct |
15 | Correct | 454 ms | 317960 KB | Output is correct |
16 | Correct | 459 ms | 316384 KB | Output is correct |
17 | Correct | 277 ms | 250888 KB | Output is correct |
18 | Correct | 278 ms | 259092 KB | Output is correct |