Submission #537933

#	Time	Username	Problem	Language	Result	Execution time	Memory
537933		new_acc	Teams (IOI15_teams)	C++14	100 / 100	2415 ms	380372 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e5+10;
const int SS=1<<19;
struct item{
	item *l,*r;
	int val;
};
pitem wsk[N];
pair<int,int>t[N];
bitset<N>ok;
int n,dp[N],w[N];
void upd(int ind,pitem v,pitem nv,int p=0,int k=SS-1){
	nv->val=v->val+1;
	if(!(v->r)){
		nv->r=nullptr,nv->l=nullptr;
		return;
	}
	if(ind<=(p+k)>>1){
		nv->r=v->r,nv->l=new item;
		upd(ind,v->l,nv->l,p,(p+k)>>1);
	}else{
		nv->l=v->l,nv->r=new item;
		upd(ind,v->r,nv->r,((p+k)>>1)+1,k);
	}
}
void build(pitem v,int akt){
	if(!v) return;
	v->val=0;
	if(akt>SS) v->l=nullptr,v->r=nullptr;
	else{
		v->r=new item,v->l=new item;
		build(v->r,(akt<<1)+1),build(v->l,(akt<<1));
	}
}
int Query(pitem v,int a,int b,int p=0,int k=SS-1){
	if(p>b or k<a) return 0;
	if(p>=a and k<=b) return v->val;
	else return Query(v->l,a,b,p,(p+k)>>1)+Query(v->r,a,b,((p+k)>>1)+1,k);
}
int bs(int x){
	int pocz=1,kon=n,res=0,sr;
	while(pocz<=kon){
		sr=(pocz+kon)>>1;
		if(t[sr].fi<=x) res=sr,pocz=sr+1;
		else kon=sr-1;
	}
	return res;
}
int sq(int a,int b){
	return Query(wsk[bs(a)],b,SS-1);
}
int bs2(int i,int j,int pocz,int kon){
	int sr,res=kon+1;
	while(pocz<=kon){
		sr=(pocz+kon)>>1;
		int val1=sq(w[sr],w[sr])-sq(w[i],w[sr])+dp[i]-w[sr];
		int val2=sq(w[sr],w[sr])-sq(w[j],w[sr])+dp[j]-w[sr];
		if(val1<=val2) kon=sr-1,res=sr;
		else pocz=sr+1;
	}
	return res;
}
void init(int nn,int a[],int b[]){
	n=nn;
	for(int i=0;i<n;i++) t[i+1]={a[i],b[i]};
	sort(t+1,t+1+n);
	wsk[0]=new item;
	build(wsk[0],1);
	for(int i=1;i<=n;i++){
		wsk[i]=new item;
		upd(t[i].se,wsk[i-1],wsk[i]);
	}
}
int can(int m,int vv[]){
	sort(vv,vv+m);
	for(int i=0;i<m;i++) w[i+1]=vv[i];
	dp[1]=sq(w[1],w[1])-w[1];
	if(m==1) return dp[1]>=0;
	for(int i=1;i<=m;i++) ok[i]=0;
	set<int> curr;
	set<pair<int,int> >act;
	ok[1]=1;
	curr.insert(1),act.insert({2,0});
	while(1){
		auto it2=act.begin();
		pair<int,int> v=*it2;
		act.erase(it2);
		if(v.fi>m) break;
		if(v.se<0){	
			v.se*=-1;
			if(!ok[v.se]) continue;
			ok[v.se]=0;
			auto it=curr.lower_bound(v.se);
			it--;			
			int mn=*it;
			it++,it++;
			if(it!=curr.end()){
				int wi=*it;
				act.insert({bs2(mn,wi,v.se+1,m),-wi});
			}
			it--;
			curr.erase(it);
		}else{
			auto it=curr.end();
			it--;
			dp[v.fi]=min(sq(w[v.fi],w[v.fi])-w[v.fi],sq(w[v.fi],w[v.fi])-sq(w[*it],w[v.fi])+dp[*it]-w[v.fi]);
			curr.insert(v.fi);
			it=curr.end();
			it--,it--;
			act.insert({bs2(*it,v.fi,v.fi+1,m),-(v.fi)});
			act.insert({v.fi+1,0});
			ok[v.fi]=1;
		}
	}
	for(int i=1;i<=m;i++) if(dp[i]<0) return 0;
	return 1;
}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23