# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
986387 |
2024-05-20T12:32:56 Z |
Pyqe |
Teams (IOI15_teams) |
C++17 |
|
1690 ms |
250012 KB |
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
int n,nsg=0,nn,fq[500069],la[30000069],ra[30000069],sma[30000069],pa[30000069][2],sg[500069],inf=1e9;
pair<int,int> a[2][500069],sk[200069];
void bd(int ix,int lh,int rh)
{
la[ix]=lh;
ra[ix]=rh;
sma[ix]=0;
if(la[ix]!=ra[ix])
{
int ii,md=(la[ix]+ra[ix])/2;
for(ii=0;ii<2;ii++)
{
nsg++;
pa[ix][ii]=nsg;
bd(nsg,!ii?la[ix]:md+1,!ii?md:ra[ix]);
}
}
}
void ud(int ix,int x,int w)
{
if(la[ix]>=x&&ra[ix]<=x)
{
sma[ix]+=w;
}
else
{
int ii,jj,p;
for(ii=0;ii<2;ii++)
{
p=pa[ix][ii];
if(la[p]<=x&&ra[p]>=x)
{
nsg++;
la[nsg]=la[p];
ra[nsg]=ra[p];
sma[nsg]=sma[p];
for(jj=0;jj<2;jj++)
{
pa[nsg][jj]=pa[p][jj];
}
pa[ix][ii]=nsg;
ud(nsg,x,w);
}
}
sma[ix]=sma[pa[ix][0]]+sma[pa[ix][1]];
}
}
int qr(int ix,int lh,int rh,int sr)
{
if(la[ix]>rh||ra[ix]<lh)
{
return 0;
}
else if(la[ix]>=lh&&ra[ix]<=rh)
{
return sma[ix]-sma[sr];
}
else
{
return qr(pa[ix][0],lh,rh,pa[sr][0])+qr(pa[ix][1],lh,rh,pa[sr][1]);
}
}
int bl(int ix,int x,int sr)
{
if(la[ix]==ra[ix])
{
return la[ix];
}
else
{
int ii,p,p2;
for(ii=0;ii<2;ii++)
{
p=pa[ix][ii];
p2=pa[sr][ii];
if(x<=sma[p]-sma[p2])
{
return bl(p,x,p2);
}
x-=sma[p]-sma[p2];
}
return -1;
}
}
void init(int on,int laa[],int raa[])
{
int i,ii,k,l;
n=on;
for(i=1;i<=n;i++)
{
k=laa[i-1];
l=raa[i-1];
a[0][i]={k,l};
}
sort(a[0]+1,a[0]+n+1);
for(i=1;i<=n;i++)
{
l=a[0][i].sc;
fq[l]++;
a[1][i]={l,fq[l]};
}
sort(a[1]+1,a[1]+n+1);
for(i=n;i;i--)
{
l=a[0][i].sc;
a[0][i].sc=lower_bound(a[1]+1,a[1]+n+1,mp(l,fq[l]))-a[1];
fq[l]--;
}
nsg++;
sg[0]=nsg;
bd(nsg,1,n);
for(i=1;i<=n;i++)
{
l=a[0][i].sc;
nsg++;
la[nsg]=la[sg[i-1]];
ra[nsg]=ra[sg[i-1]];
sma[nsg]=sma[sg[i-1]];
for(ii=0;ii<2;ii++)
{
pa[nsg][ii]=pa[sg[i-1]][ii];
}
sg[i]=nsg;
ud(nsg,l,1);
}
}
int can(int sz,int qq[])
{
int i,k,l,w,sm;
sort(qq,qq+sz);
nn=0;
for(i=0;i<sz;i++)
{
sm=qq[i];
k=upper_bound(a[0]+1,a[0]+n+1,mp(sm,inf))-a[0]-1;
l=lower_bound(a[1]+1,a[1]+n+1,mp(sm,0))-a[1]-1;
for(;nn;nn--)
{
w=qr(sg[k],l+1,sk[nn].sc-1,sg[sk[nn].fr]);
if(w>sm)
{
break;
}
l=max(l,sk[nn].sc);
sm-=w;
}
l=bl(sg[k],qr(sg[k],1,l,sg[sk[nn].fr])+sm,sg[sk[nn].fr]);
if(l==-1)
{
return 0;
}
nn++;
sk[nn]={k,l};
}
return 1;
}
Compilation message
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:124:54: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
124 | a[0][i].sc=lower_bound(a[1]+1,a[1]+n+1,mp(l,fq[l]))-a[1];
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:155:49: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
155 | k=upper_bound(a[0]+1,a[0]+n+1,mp(sm,inf))-a[0]-1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:156:47: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
156 | l=lower_bound(a[1]+1,a[1]+n+1,mp(sm,0))-a[1]-1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14684 KB |
Output is correct |
2 |
Correct |
2 ms |
14684 KB |
Output is correct |
3 |
Correct |
2 ms |
14684 KB |
Output is correct |
4 |
Correct |
2 ms |
14684 KB |
Output is correct |
5 |
Correct |
2 ms |
14684 KB |
Output is correct |
6 |
Correct |
2 ms |
14684 KB |
Output is correct |
7 |
Correct |
3 ms |
14684 KB |
Output is correct |
8 |
Correct |
2 ms |
14680 KB |
Output is correct |
9 |
Correct |
2 ms |
14684 KB |
Output is correct |
10 |
Correct |
2 ms |
14684 KB |
Output is correct |
11 |
Correct |
2 ms |
14684 KB |
Output is correct |
12 |
Correct |
3 ms |
14684 KB |
Output is correct |
13 |
Correct |
2 ms |
14788 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
2 ms |
14680 KB |
Output is correct |
16 |
Correct |
2 ms |
14680 KB |
Output is correct |
17 |
Correct |
2 ms |
14684 KB |
Output is correct |
18 |
Correct |
2 ms |
14684 KB |
Output is correct |
19 |
Correct |
2 ms |
14684 KB |
Output is correct |
20 |
Correct |
2 ms |
14684 KB |
Output is correct |
21 |
Correct |
2 ms |
14684 KB |
Output is correct |
22 |
Correct |
2 ms |
14684 KB |
Output is correct |
23 |
Correct |
2 ms |
14680 KB |
Output is correct |
24 |
Correct |
2 ms |
14684 KB |
Output is correct |
25 |
Correct |
2 ms |
14684 KB |
Output is correct |
26 |
Correct |
2 ms |
14684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
54960 KB |
Output is correct |
2 |
Correct |
89 ms |
54920 KB |
Output is correct |
3 |
Correct |
101 ms |
55184 KB |
Output is correct |
4 |
Correct |
91 ms |
55136 KB |
Output is correct |
5 |
Correct |
41 ms |
54364 KB |
Output is correct |
6 |
Correct |
42 ms |
54528 KB |
Output is correct |
7 |
Correct |
41 ms |
54540 KB |
Output is correct |
8 |
Correct |
42 ms |
54356 KB |
Output is correct |
9 |
Correct |
63 ms |
54508 KB |
Output is correct |
10 |
Correct |
47 ms |
54608 KB |
Output is correct |
11 |
Correct |
39 ms |
54532 KB |
Output is correct |
12 |
Correct |
38 ms |
54540 KB |
Output is correct |
13 |
Correct |
51 ms |
54580 KB |
Output is correct |
14 |
Correct |
50 ms |
54888 KB |
Output is correct |
15 |
Correct |
78 ms |
54944 KB |
Output is correct |
16 |
Correct |
82 ms |
54956 KB |
Output is correct |
17 |
Correct |
42 ms |
54868 KB |
Output is correct |
18 |
Correct |
50 ms |
54920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
55672 KB |
Output is correct |
2 |
Correct |
104 ms |
55216 KB |
Output is correct |
3 |
Correct |
328 ms |
58192 KB |
Output is correct |
4 |
Correct |
94 ms |
55168 KB |
Output is correct |
5 |
Correct |
129 ms |
54864 KB |
Output is correct |
6 |
Correct |
122 ms |
54868 KB |
Output is correct |
7 |
Correct |
47 ms |
54900 KB |
Output is correct |
8 |
Correct |
102 ms |
54996 KB |
Output is correct |
9 |
Correct |
64 ms |
54536 KB |
Output is correct |
10 |
Correct |
101 ms |
54796 KB |
Output is correct |
11 |
Correct |
130 ms |
54868 KB |
Output is correct |
12 |
Correct |
173 ms |
55124 KB |
Output is correct |
13 |
Correct |
272 ms |
54864 KB |
Output is correct |
14 |
Correct |
361 ms |
56660 KB |
Output is correct |
15 |
Correct |
108 ms |
55276 KB |
Output is correct |
16 |
Correct |
111 ms |
55380 KB |
Output is correct |
17 |
Correct |
76 ms |
55200 KB |
Output is correct |
18 |
Correct |
77 ms |
55120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
797 ms |
235676 KB |
Output is correct |
2 |
Correct |
797 ms |
242756 KB |
Output is correct |
3 |
Correct |
1515 ms |
250012 KB |
Output is correct |
4 |
Correct |
789 ms |
242760 KB |
Output is correct |
5 |
Correct |
526 ms |
238284 KB |
Output is correct |
6 |
Correct |
548 ms |
238780 KB |
Output is correct |
7 |
Correct |
247 ms |
238284 KB |
Output is correct |
8 |
Correct |
504 ms |
238520 KB |
Output is correct |
9 |
Correct |
365 ms |
238456 KB |
Output is correct |
10 |
Correct |
453 ms |
236764 KB |
Output is correct |
11 |
Correct |
627 ms |
237376 KB |
Output is correct |
12 |
Correct |
723 ms |
238348 KB |
Output is correct |
13 |
Correct |
1255 ms |
240364 KB |
Output is correct |
14 |
Correct |
1690 ms |
246612 KB |
Output is correct |
15 |
Correct |
649 ms |
242724 KB |
Output is correct |
16 |
Correct |
628 ms |
242864 KB |
Output is correct |
17 |
Correct |
342 ms |
241916 KB |
Output is correct |
18 |
Correct |
336 ms |
242044 KB |
Output is correct |