Submission #569733

#	Time	Username	Problem	Language	Result	Execution time	Memory
569733		CSQ31	Teams (IOI15_teams)	C++17	100 / 100	1284 ms	414384 KiB

teams

#pragma GCC optimize("Ofast") 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
const int MAXN = 5e5+5;
struct node{
	int x,lf = -1,rg = -1;
	node(){}
};
node T[MAXN*60];
int ccnt = 0;
void pull(int v){
	T[v].x = 0;
	if(T[v].lf!=-1)T[v].x+=T[T[v].lf].x;
	if(T[v].rg!=-1)T[v].x+=T[T[v].rg].x;
}
int copy(int v){
	T[++ccnt] = T[v];
	return ccnt;
}
int newnode(){
	ccnt++;
	T[ccnt].x = 0;
	T[ccnt].lf = T[ccnt].rg = -1;
	return ccnt;
	
}
int add(int v,int l,int r,int pos,int x){
	int me = copy(v);
	if(l==r){
		T[me].x+=x;
		return me;
	}
	int tm = (l+r)/2;
	if(pos<=tm){
		if(T[v].lf == -1)T[v].lf = newnode();
		T[me].lf = add(T[v].lf,l,tm,pos,x);
	}else{
		if(T[v].rg == -1)T[v].rg = newnode();
		T[me].rg = add(T[v].rg,tm+1,r,pos,x);
	}
	pull(me);
	return me;
}
int zero(int used,int l,int r,int tl,int tr){
	int v = copy(used);
	if(l<=tl && tr<=r){
		T[v].x = 0;
		T[v].lf = T[v].rg = -1;
		return v;
	}
	int tm = (tl+tr)/2;
	if(r<=tm){
		if(T[v].lf != -1)T[v].lf = zero(T[used].lf,l,r,tl,tm);
	}
	else if(l >tm){
		if(T[v].rg != -1)T[v].rg = zero(T[used].rg,l,r,tm+1,tr);
	}else{
		if(T[v].lf != -1)T[v].lf = zero(T[used].lf,l,tm,tl,tm);
		if(T[v].rg != -1)T[v].rg = zero(T[used].rg,tm+1,r,tm+1,tr);
	}
	pull(v);
	return v;
}
vector<int>seg;
int n;
bool kek = 1;
int walk(int avi,int used,int l,int r,int k){
	//cout<<l<<" "<<r<<" "<<T[avi].x<<" "<<T[used].x<<" "<<k<<'\n';
	int v = copy(used);
	if(T[avi].x - T[v].x < k || !k){
		kek = 0;
		return v;
	}
	if(l==r){
		T[v].x += k;
		return v;
	}
	int tm = (l+r)/2;
	int val = 0;
	if(T[v].lf == -1)T[v].lf = newnode();
	if(T[v].rg == -1)T[v].rg = newnode();
	if(T[avi].lf != -1)val+=T[T[avi].lf].x;
	val-=T[T[v].lf].x;
	if(val>=k)T[v].lf = walk(T[avi].lf,T[v].lf,l,tm,k);
	else{
		T[v].lf = T[avi].lf;
		T[v].rg = walk(T[avi].rg,T[v].rg,tm+1,r,k-val);
	}
	pull(v);
	return v;
}
void init(int N, int A[], int B[]) {
	n = N;
	seg.push_back(0);
	vector<map<int,int>>cnt(n+1);
	vector<int>cnt1(n+2,0);
	for(int i=0;i<n;i++){
		cnt[A[i]][B[i]]++;
		cnt1[B[i]+1]++;
	}
	for(int i=1;i<=n;i++){
		seg.push_back(copy(seg.back()));
		for(auto x:cnt[i]){
			//cout<<i<<" "<<x.fi<<" "<<x.se<<'\n';
			seg.back() = add(seg.back(),1,n,x.fi,x.se);
		}
		if(cnt1[i])seg.back() = add(seg.back(),1,n,i-1,-cnt1[i]);
	}
}
int can(int m, int K[]) {
	int sum = 0;
	map<int,int>cnt;
	for(int i=0;i<m;i++){
		sum+=K[i];
		cnt[K[i]]++;
		if(sum>n)return 0;
	}
	vector<pii>a;
	for(auto x:cnt)a.push_back(x);
	int old = ccnt;
	int used = newnode();
	kek = 1;
	for(auto x:a){
		//cout<<x.fi<<" "<<x.se<<'\n';
		if(x.fi>1)used = zero(used,1,x.fi-1,1,n);
		used = walk(seg[x.fi],used,1,n,x.fi*x.se);
		if(!kek)break;
	}
	for(int i=old+1;i<=ccnt;i++){
		T[i].x = 0;
		T[i].lf = T[i].rg = -1;
	}
	ccnt = old;
	return kek;
}

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