Submission #931747

#	Time	Username	Problem	Language	Result	Execution time	Memory
931747		winter0101	Teams (IOI15_teams)	C++17	77 / 100	3156 ms	524288 KiB

teams

#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[20000009];
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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23