oj.uz

Submission #931763

# Submission time Handle Problem Language Result Execution time Memory
931763 2024-02-22T10:36:08 Z winter0101 Teams (IOI15_teams) C++14
34 / 100
 1366 ms 414604 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){
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 (cost+val>=need)return walk(st[id1].l,st[id2].l,l,mid,val,need);
return walk(st[id1].r,st[id2].r,mid+1,r,val,need-cost);
}
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);
//cout<<v<<" "<<ans<<'\n';
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 119 ms 376404 KB Output is correct
2 Correct 113 ms 376404 KB Output is correct
3 Correct 114 ms 376400 KB Output is correct
4 Correct 114 ms 376404 KB Output is correct
5 Correct 111 ms 376244 KB Output is correct
6 Correct 113 ms 376268 KB Output is correct
7 Correct 112 ms 376404 KB Output is correct
8 Correct 113 ms 376404 KB Output is correct
9 Correct 112 ms 376404 KB Output is correct
10 Correct 111 ms 376320 KB Output is correct
11 Correct 112 ms 376404 KB Output is correct
12 Correct 111 ms 376400 KB Output is correct
13 Correct 113 ms 376420 KB Output is correct
14 Correct 111 ms 376220 KB Output is correct
15 Correct 114 ms 376216 KB Output is correct
16 Correct 110 ms 376328 KB Output is correct
17 Correct 111 ms 376400 KB Output is correct
18 Correct 112 ms 376220 KB Output is correct
19 Correct 110 ms 376400 KB Output is correct
20 Correct 115 ms 376400 KB Output is correct
21 Correct 116 ms 376404 KB Output is correct
22 Correct 114 ms 376352 KB Output is correct
23 Correct 112 ms 376400 KB Output is correct
24 Correct 112 ms 376348 KB Output is correct
25 Correct 111 ms 376400 KB Output is correct
26 Correct 112 ms 376400 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 382396 KB Output is correct
2 Correct 192 ms 382292 KB Output is correct
3 Correct 195 ms 382256 KB Output is correct
4 Correct 204 ms 383360 KB Output is correct
5 Correct 157 ms 379732 KB Output is correct
6 Correct 155 ms 379728 KB Output is correct
7 Correct 162 ms 379728 KB Output is correct
8 Correct 156 ms 379888 KB Output is correct
9 Correct 137 ms 379872 KB Output is correct
10 Correct 168 ms 379844 KB Output is correct
11 Correct 156 ms 379588 KB Output is correct
12 Correct 159 ms 379532 KB Output is correct
13 Correct 164 ms 379976 KB Output is correct
14 Correct 159 ms 380988 KB Output is correct
15 Correct 190 ms 382020 KB Output is correct
16 Correct 188 ms 382036 KB Output is correct
17 Correct 162 ms 379984 KB Output is correct
18 Correct 160 ms 379620 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 382608 KB Output is correct
2 Correct 221 ms 382912 KB Output is correct
3 Correct 328 ms 385876 KB Output is correct
4 Correct 198 ms 383260 KB Output is correct
5 Correct 195 ms 380240 KB Output is correct
6 Correct 208 ms 380164 KB Output is correct
7 Correct 160 ms 380312 KB Output is correct
8 Correct 186 ms 380212 KB Output is correct
9 Correct 136 ms 380016 KB Output is correct
10 Correct 161 ms 380108 KB Output is correct
11 Correct 169 ms 379924 KB Output is correct
12 Correct 232 ms 380028 KB Output is correct
13 Correct 273 ms 380336 KB Output is correct
14 Correct 348 ms 384052 KB Output is correct
15 Correct 225 ms 382560 KB Output is correct
16 Correct 224 ms 382516 KB Output is correct
17 Correct 186 ms 380176 KB Output is correct
18 Incorrect 185 ms 380108 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 802 ms 406532 KB Output is correct
2 Correct 797 ms 406672 KB Output is correct
3 Correct 1304 ms 414604 KB Output is correct
4 Correct 773 ms 407764 KB Output is correct
5 Correct 437 ms 393940 KB Output is correct
6 Correct 429 ms 394320 KB Output is correct
7 Correct 359 ms 393968 KB Output is correct
8 Correct 420 ms 393840 KB Output is correct
9 Correct 258 ms 394160 KB Output is correct
10 Correct 365 ms 392628 KB Output is correct
11 Correct 441 ms 392632 KB Output is correct
12 Correct 658 ms 392616 KB Output is correct
13 Correct 896 ms 395176 KB Output is correct
14 Correct 1366 ms 409060 KB Output is correct
15 Correct 745 ms 410632 KB Output is correct
16 Correct 715 ms 410828 KB Output is correct
17 Correct 449 ms 400460 KB Output is correct
18 Incorrect 438 ms 400320 KB Output isn't correct
19 Halted 0 ms 0 KB -