# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
640011 |
2022-09-13T08:43:18 Z |
ggoh |
Teams (IOI15_teams) |
C++14 |
|
939 ms |
168316 KB |
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
int n,sz;
vector<int>G[500005];
struct PST{
int l,r,val;
}T[11000000];
int root[500005];
void initree(int num,int s,int e)
{
if(s==e)return ;
T[num].l=sz;
T[sz++]={-1,-1,0};
T[num].r=sz;
T[sz++]={-1,-1,0};
initree(T[num].l,s,(s+e)/2);
initree(T[num].r,(s+e)/2+1,e);
}
void update(int par,int num,int s,int e,int x)
{
T[num].val=T[par].val+1;
if(s==e)return ;
if(x<=(s+e)/2)
{
T[num].r=T[par].r;
T[num].l=sz;
T[sz++]={-1,-1,0};
update(T[par].l,T[num].l,s,(s+e)/2,x);
}
else
{
T[num].l=T[par].l;
T[num].r=sz;
T[sz++]={-1,-1,0};
update(T[par].r,T[num].r,(s+e)/2+1,e,x);
}
}
struct D{
int A,B;
}d[500005];
int go[500005];
bool cmp(D a,D b){return a.B<b.B;}
void init(int N, int A[], int B[]) {
n=N;
for(int i=0;i<n;i++)
{
d[i]={A[i],B[i]};
go[i+1]=1e9;
}
sort(d,d+n,cmp);
for(int i=0;i<n;i++)
{
go[d[i].B]=min(go[d[i].B],i+1);
G[d[i].A].push_back(i+1);
}
for(int i=n-1;i>=1;i--)go[i]=min(go[i],go[i+1]);
root[0]=sz;
T[sz++]={-1,-1,0};
initree(0,1,n);
for(int i=1;i<=n;i++)
{
if(!sz(G[i]))
{
root[i]=root[i-1];
continue;
}
int prev=root[i-1];
for(auto &k:G[i])
{
root[i]=sz;
T[sz++]={-1,-1,0};
update(prev,root[i],1,n,k);
prev=root[i];
}
}
}
int KTH,SZ;
struct C{
int num1,num2,s,e,val;
}ST[50];
void getsum(int num1,int num2,int s,int e,int x1,int x2)
{
if(s>x2||x1>e)return ;
if(!T[num1].val && !T[num2].val)return ;
if(x1<=s&&e<=x2)
{
ST[SZ++]={num1,num2,s,e,T[num2].val-T[num1].val};
return ;
}
getsum(T[num1].l,T[num2].l,s,(s+e)/2,x1,x2);
getsum(T[num1].r,T[num2].r,(s+e)/2+1,e,x1,x2);
}
int getind(int num1,int num2,int s,int e,int x1,int x2)
{
if(s==e)
{
KTH--;
return s;
}
if(T[T[num2].l].val-T[T[num1].l].val>=KTH)
{
return getind(T[num1].l,T[num2].l,s,(s+e)/2,x1,x2);
}
else
{
KTH-=T[T[num2].l].val-T[T[num1].l].val;
return getind(T[num1].r,T[num2].r,(s+e)/2+1,e,x1,x2);
}
}
int getK(int x1,int x2,int y1,int y2)
{
SZ=0;
getsum(root[y1-1],root[y2],1,n,x1,x2);
for(int i=0;i<SZ;i++)
{
if(KTH>ST[i].val)KTH-=ST[i].val;
else
{
return getind(ST[i].num1,ST[i].num2,ST[i].s,ST[i].e,x1,x2);
}
}
return 1;
}
pii st[200002];
int stsz;
int can(int M, int K[]) {
lint sum=0;
for(int i=0;i<M;i++)sum+=K[i];
if(sum>n)return 0;
int ans=1,t;
sort(K,K+M);
t=K[0];
vector<pii>V;
for(int i=1;i<M;i++)
{
if(K[i]==K[i-1])
{
t+=K[i];
}
else
{
V.push_back({K[i-1],t});
t=K[i];
}
}
V.push_back({K[M-1],t});
int m=sz(V);
stsz=0;
for(int i=0;i<m;i++)
{
while(stsz>0 && st[stsz-1].second<go[V[i].first])stsz--;
KTH=V[i].second;
int prev=go[V[i].first];
while(stsz>=0)
{
if(stsz>0)t=getK(prev,st[stsz-1].second,st[stsz-1].first+1,V[i].first);
else t=getK(prev,n,1,V[i].first);
if(KTH>0)
{
if(stsz)prev=st[stsz-1].second+1;
stsz--;
}
else
{
st[stsz++]={V[i].first,t};
break;
}
}
if(stsz==-1)
{
ans=0;
break;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
12028 KB |
Output is correct |
3 |
Correct |
7 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
12108 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
12116 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
8 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12096 KB |
Output is correct |
10 |
Correct |
6 ms |
12004 KB |
Output is correct |
11 |
Correct |
6 ms |
12100 KB |
Output is correct |
12 |
Correct |
6 ms |
11988 KB |
Output is correct |
13 |
Correct |
7 ms |
12040 KB |
Output is correct |
14 |
Correct |
6 ms |
12024 KB |
Output is correct |
15 |
Correct |
7 ms |
12008 KB |
Output is correct |
16 |
Correct |
6 ms |
11988 KB |
Output is correct |
17 |
Correct |
6 ms |
11988 KB |
Output is correct |
18 |
Correct |
6 ms |
11988 KB |
Output is correct |
19 |
Correct |
6 ms |
11988 KB |
Output is correct |
20 |
Correct |
6 ms |
12088 KB |
Output is correct |
21 |
Correct |
6 ms |
11988 KB |
Output is correct |
22 |
Correct |
6 ms |
12084 KB |
Output is correct |
23 |
Correct |
6 ms |
11988 KB |
Output is correct |
24 |
Correct |
6 ms |
11988 KB |
Output is correct |
25 |
Correct |
6 ms |
12088 KB |
Output is correct |
26 |
Correct |
7 ms |
11988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
39324 KB |
Output is correct |
2 |
Correct |
62 ms |
39248 KB |
Output is correct |
3 |
Correct |
66 ms |
39244 KB |
Output is correct |
4 |
Correct |
64 ms |
39724 KB |
Output is correct |
5 |
Correct |
37 ms |
38092 KB |
Output is correct |
6 |
Correct |
38 ms |
38100 KB |
Output is correct |
7 |
Correct |
38 ms |
38092 KB |
Output is correct |
8 |
Correct |
40 ms |
38092 KB |
Output is correct |
9 |
Correct |
34 ms |
38160 KB |
Output is correct |
10 |
Correct |
35 ms |
37952 KB |
Output is correct |
11 |
Correct |
33 ms |
37948 KB |
Output is correct |
12 |
Correct |
37 ms |
37956 KB |
Output is correct |
13 |
Correct |
51 ms |
38252 KB |
Output is correct |
14 |
Correct |
48 ms |
38468 KB |
Output is correct |
15 |
Correct |
57 ms |
39116 KB |
Output is correct |
16 |
Correct |
59 ms |
39184 KB |
Output is correct |
17 |
Correct |
39 ms |
38088 KB |
Output is correct |
18 |
Correct |
41 ms |
38020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
74 ms |
39668 KB |
Output is correct |
2 |
Correct |
71 ms |
39636 KB |
Output is correct |
3 |
Correct |
184 ms |
42620 KB |
Output is correct |
4 |
Correct |
65 ms |
39668 KB |
Output is correct |
5 |
Correct |
81 ms |
38464 KB |
Output is correct |
6 |
Correct |
75 ms |
38488 KB |
Output is correct |
7 |
Correct |
45 ms |
38496 KB |
Output is correct |
8 |
Correct |
69 ms |
38392 KB |
Output is correct |
9 |
Correct |
37 ms |
37956 KB |
Output is correct |
10 |
Correct |
36 ms |
38220 KB |
Output is correct |
11 |
Correct |
43 ms |
38316 KB |
Output is correct |
12 |
Correct |
135 ms |
38280 KB |
Output is correct |
13 |
Correct |
211 ms |
38632 KB |
Output is correct |
14 |
Correct |
220 ms |
40924 KB |
Output is correct |
15 |
Correct |
93 ms |
39612 KB |
Output is correct |
16 |
Correct |
90 ms |
39688 KB |
Output is correct |
17 |
Correct |
62 ms |
38356 KB |
Output is correct |
18 |
Correct |
66 ms |
38356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
467 ms |
162432 KB |
Output is correct |
2 |
Correct |
445 ms |
162384 KB |
Output is correct |
3 |
Correct |
806 ms |
168316 KB |
Output is correct |
4 |
Correct |
444 ms |
162508 KB |
Output is correct |
5 |
Correct |
275 ms |
156108 KB |
Output is correct |
6 |
Correct |
270 ms |
156012 KB |
Output is correct |
7 |
Correct |
195 ms |
156028 KB |
Output is correct |
8 |
Correct |
257 ms |
156072 KB |
Output is correct |
9 |
Correct |
159 ms |
155196 KB |
Output is correct |
10 |
Correct |
161 ms |
155332 KB |
Output is correct |
11 |
Correct |
227 ms |
155400 KB |
Output is correct |
12 |
Correct |
494 ms |
155520 KB |
Output is correct |
13 |
Correct |
899 ms |
157288 KB |
Output is correct |
14 |
Correct |
939 ms |
164176 KB |
Output is correct |
15 |
Correct |
441 ms |
160952 KB |
Output is correct |
16 |
Correct |
421 ms |
161060 KB |
Output is correct |
17 |
Correct |
250 ms |
155844 KB |
Output is correct |
18 |
Correct |
254 ms |
155944 KB |
Output is correct |