Submission #1017812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017812		amirhoseinfar1385	Teams (IOI15_teams)	C++17	100 / 100	2772 ms	325552 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10,lg=20,kaf=(1<<lg),maxq=maxn;
vector<pair<int,int>>alle;
int n,dproot[maxn],root,m;
vector<int>ezaf[maxn];
vector<int>all;
vector<pair<int,int>>unnow;

struct segment{
	struct node{
		int cl,cr,w;
		node(){
			w=0;
			cl=cr=0;
		}
	};
	node seg[maxq*lg];
	int te=1;
	vector<int>hey,hey2;
	int upd(int i,int l,int r,int tl,int tr,int w){
		while(true){
			int u=te;
			seg[te]=seg[i];
			te++;
			if(l>=tl&&r<=tr){
				seg[u].w+=w;
				int last=u;
				while((int)hey.size()>0){
					if(hey2.back()==0){
						seg[hey.back()].cl=last;
					}else{
						seg[hey.back()].cr=last;
					}
					last=hey.back();
					seg[last].w=seg[seg[last].cl].w+seg[seg[last].cr].w;
					hey.pop_back();
					hey2.pop_back();
				}
				return last;
			}
			int mid=(l+r)>>1;
			if(tl<=mid){
				hey.push_back(u);
				hey2.push_back(0);
				i=u=seg[u].cl;
				r=mid;
				//seg[u].cl=upd(seg[u].cl,l,mid,tl,tr,w);
			}else{
				hey.push_back(u);
				hey2.push_back(1);
				i=u=seg[u].cr;
				l=mid+1;
				//seg[u].cr=upd(seg[u].cr,mid+1,r,tl,tr,w);
			}
			//seg[u].w=seg[seg[u].cl].w+seg[seg[u].cr].w;
		}
		return 0;
	}
	int pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		if(l>=tl&&r<=tr){
			return seg[i].w;
		}
		int mid=(l+r)>>1;
		return pors(seg[i].cl,l,mid,tl,tr)+pors(seg[i].cr,mid+1,r,tl,tr);
	}
}seg;
vector<pair<int,int>>tof;

void init(int N, int A[], int B[]) {
	n=N;
	set<pair<int,int>>st;
	tof.push_back(make_pair(0,0));
	for(int i=0;i<n;i++){
		tof.push_back(make_pair(A[i],i));
		tof.push_back(make_pair(B[i],i+n));
	}
	sort(tof.begin(),tof.end());
	for(int i=0;i<(int)tof.size();i++){
		if(tof[i].second<n){
			A[tof[i].second]=i;
		}else{
			B[tof[i].second-n]=i;
		}
	}
	for(int i=0;i<n;i++){
	//	cout<<"hey: "<<A[i]<<" "<<B[i]<<" "<<i<<endl;
		alle.push_back(make_pair(A[i],B[i]));
		ezaf[alle[i].second].push_back(alle[i].first);
		st.insert(alle.back());
	}
	for(int i=1;i<maxn;i++){
		for(auto x:ezaf[i]){
			root=seg.upd(root,0,kaf-1,x,x,1);
		}
		dproot[i]=root;
	}
}

int upd(int w,int ind,int mn=0){
	if((int)unnow.size()==0){
		return 0;
	}
	int z=seg.pors(dproot[unnow.back().second],0,kaf-1,unnow.back().first,ind)-seg.pors(dproot[mn],0,kaf-1,unnow.back().first,ind);
	if(unnow.back().second<=mn){
		unnow.pop_back();
		return upd(w,ind,mn);
	}
	if(z<w){
		w-=z;
		int f=unnow.back().second;
		unnow.pop_back();
		return upd(w,ind,max(f,mn));
	}
	int low=mn,high=unnow.back().second+1,mid;
	while(high-low>1){
		mid=(high+low)>>1;
		z=seg.pors(dproot[mid],0,kaf-1,unnow.back().first,ind)-seg.pors(dproot[mn],0,kaf-1,unnow.back().first,ind);
		if(z>w){
			high=mid;
		}else{
			low=mid;
		}
	}
	int ez=low;
	low=unnow.back().first,high=ind+1;
	/*while(high-low>1){
		mid=(high+low)>>1;
		z=seg.pors(dproot[ez],0,kaf-1,unnow.back().first,mid)+seg.pors(dproot[ez-1],0,kaf-1,mid+1,ind)-seg.pors(dproot[mn],0,kaf-1,unnow.back().first,ind);
		if(z>w){
			high=mid;
		}else{
			low=mid;
		}
	}*/
	low=ind;
	unnow.push_back(make_pair(low+1,ez));
	if(low!=ind){
		unnow.push_back(make_pair(ind+1,ez-1));
	}
	return 1;
}

int can(int M, int K[]) {
	m=M;
	all.clear();
	for(int i=0;i<m;i++){
		all.push_back(K[i]);
	}
	sort(all.begin(),all.end());
	unnow.clear();
	unnow.push_back(make_pair(0,(int)tof.size()+1));
	for(int i=0;i<m;i++){
		int indl=(int)(lower_bound(tof.begin(),tof.end(),make_pair(all[i],-1))-tof.begin()),indr=(int)(lower_bound(tof.begin(),tof.end(),make_pair(all[i]+1,-1))-tof.begin())-1;
		//cout<<indl<<" "<<indr<<" "<<all[i]<<endl;
		unnow.push_back(make_pair(indr+1,indl-1));
		if(upd(all[i],indr,0)==0){
			return 0;
		}
	}
	return 1;
}

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