oj.uz

Submission #931812

# Submission time Handle Problem Language Result Execution time Memory
931812 2024-02-22T11:16:10 Z winter0101 Teams (IOI15_teams) C++14
100 / 100
 1317 ms 414540 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
struct node{
int l,r,val;
node(){
l=r=-1,val=0;
}
}st[30000009];
int nnode=0;
int build(int id,int l,int r){
if (l==r)return id;
int mid=(l+r)>>1;
st[id].l=build(id<<1,l,mid);
st[id].r=build(id<<1|1,mid+1,r);
return id;
}
int copy(int id){
st[++nnode]=st[id];
return nnode;
}
int update(int id,int l,int r,int u,int val){
if (l>u||r<u)return id;
if (l==r){
int newnode=copy(id);
st[newnode].val+=val;
return newnode;
}
int mid=(l+r)>>1;
int newnode=copy(id);
st[newnode].l=update(st[id].l,l,mid,u,val);
st[newnode].r=update(st[id].r,mid+1,r,u,val);
st[newnode].val=st[st[newnode].l].val+st[st[newnode].r].val;
return newnode;
}
int update_range(int id1,int id2,int l,int r,int u,int v){
if (l>v||r<u||u>v)return id1;
if (u<=l&&r<=v)return id2;
int mid=(l+r)>>1;
int newnode=copy(id1);
st[newnode].l=update_range(st[id1].l,st[id2].l,l,mid,u,v);
st[newnode].r=update_range(st[id1].r,st[id2].r,mid+1,r,u,v);
st[newnode].val=st[st[newnode].l].val+st[st[newnode].r].val;
return newnode;
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return st[id].val;
int mid=(l+r)>>1;
return get(st[id].l,l,mid,u,v)+get(st[id].r,mid+1,r,u,v);
}
int walk(int id1,int id2,int l,int r,int val,int need,int xxx){
if (st[id1].val-st[id2].val+val<need)return -1;
if (l==r)return l;
int mid=(l+r)>>1;
int cost=st[st[id1].l].val-st[st[id2].l].val;
if (mid>=xxx){
if (cost+val>=need)return walk(st[id1].l,st[id2].l,l,mid,val,need,xxx);
else return walk(st[id1].r,st[id2].r,mid+1,r,0,need-(val+cost),xxx);
}
else {
return walk(st[id1].r,st[id2].r,mid+1,r,val+st[st[id1].l].val-st[st[id2].l].val,need,xxx);
}
}
const int maxn=5e5+9;
pii a[maxn];
int req[maxn];
int root[maxn];
vector<int>add[maxn],del[maxn];
int n;
void init(int N, int A[], int B[]) {
n=N;
for1(i,1,n){
a[i].fi=A[i-1],a[i].se=B[i-1];
}
sort(a+1,a+1+n,[](pii p,pii q){
if (p.se==q.se)return p.fi<q.fi;
return p.se<q.se;
});
for1(i,1,n){
add[a[i].fi].pb(i);
del[a[i].se+1].pb(i);
int l=1,r=n;
req[i]=n+1;
while (l<=r){
int mid=(l+r)/2;
if (a[mid].se>=i){
req[i]=mid;
r=mid-1;
}
else l=mid+1;
}
}
root[0]=build(1,1,n);
nnode=4*n;
for1(i,1,n){
int rt=root[i-1];
for(auto v:add[i]){
rt=update(rt,1,n,v,1);
}
for (auto v:del[i]){
rt=update(rt,1,n,v,-1);
}
root[i]=rt;
}
}
int cnt[maxn];
int can(int M, int K[]) {
int now=root[0],num=nnode;
long long sum=0;
for1(i,0,M-1)sum+=K[i];
if (sum>n)return 0;
for1(i,0,M-1)cnt[K[i]]++;
vector<int>gr;
for1(i,0,M-1)gr.pb(K[i]);
sort(all(gr));
gr.resize(distance(gr.begin(),unique(all(gr))));
bool fl=true;
for (auto v:gr){
int ans=walk(root[v],now,1,n,-get(root[v],1,n,1,req[v]-1)+get(now,1,n,1,req[v]-1),cnt[v]*v,req[v]);
if (ans==-1){
fl=false;
break;
}
now=update_range(now,root[v],1,n,req[v],ans);
}
nnode=num;
for1(i,0,M-1)cnt[K[i]]=0;
return fl;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 376252 KB Output is correct
2 Correct 110 ms 376300 KB Output is correct
3 Correct 112 ms 376404 KB Output is correct
4 Correct 111 ms 376320 KB Output is correct
5 Correct 111 ms 376252 KB Output is correct
6 Correct 115 ms 376404 KB Output is correct
7 Correct 111 ms 376404 KB Output is correct
8 Correct 112 ms 376660 KB Output is correct
9 Correct 111 ms 376444 KB Output is correct
10 Correct 112 ms 376336 KB Output is correct
11 Correct 110 ms 376388 KB Output is correct
12 Correct 115 ms 376348 KB Output is correct
13 Correct 112 ms 376408 KB Output is correct
14 Correct 112 ms 376276 KB Output is correct
15 Correct 112 ms 376460 KB Output is correct
16 Correct 115 ms 376656 KB Output is correct
17 Correct 119 ms 376400 KB Output is correct
18 Correct 112 ms 376400 KB Output is correct
19 Correct 111 ms 376396 KB Output is correct
20 Correct 114 ms 376320 KB Output is correct
21 Correct 110 ms 376436 KB Output is correct
22 Correct 110 ms 376404 KB Output is correct
23 Correct 112 ms 376404 KB Output is correct
24 Correct 111 ms 376416 KB Output is correct
25 Correct 110 ms 376400 KB Output is correct
26 Correct 114 ms 376276 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 382224 KB Output is correct
2 Correct 196 ms 382312 KB Output is correct
3 Correct 196 ms 382168 KB Output is correct
4 Correct 199 ms 383400 KB Output is correct
5 Correct 157 ms 379852 KB Output is correct
6 Correct 156 ms 379728 KB Output is correct
7 Correct 157 ms 379732 KB Output is correct
8 Correct 157 ms 379708 KB Output is correct
9 Correct 149 ms 380096 KB Output is correct
10 Correct 156 ms 379844 KB Output is correct
11 Correct 156 ms 379592 KB Output is correct
12 Correct 159 ms 379508 KB Output is correct
13 Correct 167 ms 379972 KB Output is correct
14 Correct 155 ms 380748 KB Output is correct
15 Correct 196 ms 382032 KB Output is correct
16 Correct 186 ms 382036 KB Output is correct
17 Correct 156 ms 379828 KB Output is correct
18 Correct 160 ms 379736 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 382644 KB Output is correct
2 Correct 200 ms 382548 KB Output is correct
3 Correct 331 ms 386084 KB Output is correct
4 Correct 198 ms 383184 KB Output is correct
5 Correct 228 ms 380260 KB Output is correct
6 Correct 222 ms 380316 KB Output is correct
7 Correct 159 ms 380240 KB Output is correct
8 Correct 207 ms 380240 KB Output is correct
9 Correct 138 ms 380296 KB Output is correct
10 Correct 159 ms 380100 KB Output is correct
11 Correct 163 ms 379848 KB Output is correct
12 Correct 231 ms 380004 KB Output is correct
13 Correct 286 ms 380484 KB Output is correct
14 Correct 339 ms 384336 KB Output is correct
15 Correct 218 ms 382548 KB Output is correct
16 Correct 219 ms 382388 KB Output is correct
17 Correct 192 ms 380208 KB Output is correct
18 Correct 185 ms 380232 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 406904 KB Output is correct
2 Correct 810 ms 406612 KB Output is correct
3 Correct 1258 ms 414540 KB Output is correct
4 Correct 805 ms 407600 KB Output is correct
5 Correct 521 ms 393836 KB Output is correct
6 Correct 503 ms 393812 KB Output is correct
7 Correct 359 ms 393836 KB Output is correct
8 Correct 477 ms 394164 KB Output is correct
9 Correct 249 ms 393948 KB Output is correct
10 Correct 360 ms 392604 KB Output is correct
11 Correct 419 ms 392624 KB Output is correct
12 Correct 652 ms 392796 KB Output is correct
13 Correct 893 ms 395068 KB Output is correct
14 Correct 1317 ms 409040 KB Output is correct
15 Correct 714 ms 403472 KB Output is correct
16 Correct 707 ms 403660 KB Output is correct
17 Correct 452 ms 393420 KB Output is correct
18 Correct 447 ms 393568 KB Output is correct