oj.uz

Submission #931744

# Submission time Handle Problem Language Result Execution time Memory
931744 2024-02-22T10:22:51 Z winter0101 Teams (IOI15_teams) C++14
77 / 100
 4000 ms 364032 KB 
#include<bits/stdc++.h>
#include "teams.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[25000009];
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);
}
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]=0;
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[]) {
long long sum=0;
for1(i,0,M-1)sum+=K[i];
if (sum>n)return 0;
int now=root[0],num=nnode;
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 l=req[v],r=n,ans=-1;
while (l<=r){
int mid=(l+r)>>1;
if (get(root[v],1,n,req[v],mid)-get(now,1,n,req[v],mid)>=cnt[v]*v){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
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 111 ms 317536 KB Output is correct
2 Correct 94 ms 317624 KB Output is correct
3 Correct 95 ms 317524 KB Output is correct
4 Correct 95 ms 317588 KB Output is correct
5 Correct 95 ms 317636 KB Output is correct
6 Correct 97 ms 317776 KB Output is correct
7 Correct 98 ms 317732 KB Output is correct
8 Correct 96 ms 317524 KB Output is correct
9 Correct 95 ms 317520 KB Output is correct
10 Correct 96 ms 317524 KB Output is correct
11 Correct 96 ms 317524 KB Output is correct
12 Correct 97 ms 317640 KB Output is correct
13 Correct 98 ms 317524 KB Output is correct
14 Correct 96 ms 317504 KB Output is correct
15 Correct 98 ms 317752 KB Output is correct
16 Correct 99 ms 317524 KB Output is correct
17 Correct 99 ms 317748 KB Output is correct
18 Correct 97 ms 317508 KB Output is correct
19 Correct 97 ms 317524 KB Output is correct
20 Correct 95 ms 317552 KB Output is correct
21 Correct 97 ms 317552 KB Output is correct
22 Correct 94 ms 317660 KB Output is correct
23 Correct 96 ms 317700 KB Output is correct
24 Correct 95 ms 317612 KB Output is correct
25 Correct 95 ms 317520 KB Output is correct
26 Correct 96 ms 317524 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 323668 KB Output is correct
2 Correct 184 ms 325204 KB Output is correct
3 Correct 176 ms 324620 KB Output is correct
4 Correct 187 ms 325896 KB Output is correct
5 Correct 144 ms 321876 KB Output is correct
6 Correct 140 ms 321872 KB Output is correct
7 Correct 141 ms 321872 KB Output is correct
8 Correct 142 ms 321872 KB Output is correct
9 Correct 124 ms 322092 KB Output is correct
10 Correct 142 ms 321480 KB Output is correct
11 Correct 143 ms 321568 KB Output is correct
12 Correct 180 ms 321456 KB Output is correct
13 Correct 151 ms 322180 KB Output is correct
14 Correct 172 ms 323036 KB Output is correct
15 Correct 179 ms 324492 KB Output is correct
16 Correct 174 ms 324436 KB Output is correct
17 Correct 142 ms 322128 KB Output is correct
18 Correct 146 ms 322132 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 324132 KB Output is correct
2 Correct 197 ms 325400 KB Output is correct
3 Correct 1018 ms 329224 KB Output is correct
4 Correct 186 ms 325864 KB Output is correct
5 Correct 674 ms 322716 KB Output is correct
6 Correct 614 ms 322612 KB Output is correct
7 Correct 146 ms 322684 KB Output is correct
8 Correct 498 ms 323016 KB Output is correct
9 Correct 122 ms 322116 KB Output is correct
10 Correct 150 ms 322212 KB Output is correct
11 Correct 162 ms 321952 KB Output is correct
12 Correct 714 ms 322700 KB Output is correct
13 Correct 922 ms 323140 KB Output is correct
14 Correct 1154 ms 327248 KB Output is correct
15 Correct 471 ms 325204 KB Output is correct
16 Correct 464 ms 325168 KB Output is correct
17 Correct 415 ms 323112 KB Output is correct
18 Correct 373 ms 322764 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 348384 KB Output is correct
2 Correct 788 ms 355296 KB Output is correct
3 Correct 3925 ms 364032 KB Output is correct
4 Correct 767 ms 356052 KB Output is correct
5 Correct 1751 ms 339796 KB Output is correct
6 Correct 1629 ms 340312 KB Output is correct
7 Correct 355 ms 339976 KB Output is correct
8 Correct 1395 ms 340124 KB Output is correct
9 Correct 231 ms 340180 KB Output is correct
10 Correct 343 ms 337076 KB Output is correct
11 Correct 721 ms 337588 KB Output is correct
12 Correct 2559 ms 338492 KB Output is correct
13 Correct 3783 ms 342600 KB Output is correct
14 Execution timed out 4090 ms 357896 KB Time limit exceeded
15 Halted 0 ms 0 KB -