oj.uz

Submission #931762

# Submission time Handle Problem Language Result Execution time Memory
931762 2024-02-22T10:35:49 Z winter0101 Teams (IOI15_teams) C++14
34 / 100
 560 ms 349956 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[10000009];
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 47 ms 148816 KB Output is correct
2 Correct 31 ms 148820 KB Output is correct
3 Correct 32 ms 148816 KB Output is correct
4 Correct 31 ms 148820 KB Output is correct
5 Correct 31 ms 148812 KB Output is correct
6 Correct 31 ms 148828 KB Output is correct
7 Correct 30 ms 148828 KB Output is correct
8 Correct 30 ms 148872 KB Output is correct
9 Correct 30 ms 149000 KB Output is correct
10 Correct 30 ms 148804 KB Output is correct
11 Correct 30 ms 148824 KB Output is correct
12 Correct 30 ms 148816 KB Output is correct
13 Correct 30 ms 148820 KB Output is correct
14 Correct 31 ms 148820 KB Output is correct
15 Correct 29 ms 148828 KB Output is correct
16 Correct 29 ms 148812 KB Output is correct
17 Correct 34 ms 148800 KB Output is correct
18 Correct 30 ms 148820 KB Output is correct
19 Correct 30 ms 148828 KB Output is correct
20 Correct 29 ms 148760 KB Output is correct
21 Correct 30 ms 148860 KB Output is correct
22 Correct 31 ms 148836 KB Output is correct
23 Correct 29 ms 148828 KB Output is correct
24 Correct 29 ms 148816 KB Output is correct
25 Correct 32 ms 148816 KB Output is correct
26 Correct 30 ms 148828 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 153164 KB Output is correct
2 Correct 116 ms 153172 KB Output is correct
3 Correct 113 ms 153240 KB Output is correct
4 Correct 124 ms 154252 KB Output is correct
5 Correct 73 ms 150680 KB Output is correct
6 Correct 74 ms 150612 KB Output is correct
7 Correct 75 ms 150608 KB Output is correct
8 Correct 74 ms 150612 KB Output is correct
9 Correct 54 ms 150748 KB Output is correct
10 Correct 73 ms 150724 KB Output is correct
11 Correct 76 ms 150668 KB Output is correct
12 Correct 78 ms 150388 KB Output is correct
13 Correct 83 ms 150860 KB Output is correct
14 Correct 77 ms 152136 KB Output is correct
15 Correct 107 ms 152916 KB Output is correct
16 Correct 110 ms 152832 KB Output is correct
17 Correct 81 ms 150764 KB Output is correct
18 Correct 78 ms 150528 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 153516 KB Output is correct
2 Correct 120 ms 153424 KB Output is correct
3 Correct 257 ms 156648 KB Output is correct
4 Correct 119 ms 154092 KB Output is correct
5 Correct 111 ms 151120 KB Output is correct
6 Correct 107 ms 151052 KB Output is correct
7 Correct 78 ms 151120 KB Output is correct
8 Correct 105 ms 151124 KB Output is correct
9 Correct 55 ms 150980 KB Output is correct
10 Correct 81 ms 150936 KB Output is correct
11 Correct 86 ms 150652 KB Output is correct
12 Correct 152 ms 150900 KB Output is correct
13 Correct 193 ms 151120 KB Output is correct
14 Correct 259 ms 154708 KB Output is correct
15 Correct 137 ms 153424 KB Output is correct
16 Correct 140 ms 153308 KB Output is correct
17 Correct 106 ms 150868 KB Output is correct
18 Incorrect 105 ms 150988 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 560 ms 349956 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -