Submission #1017630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017630		amirhoseinfar1385	Teams (IOI15_teams)	C++17	0 / 100	2851 ms	483624 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10,lg=19,kaf=(1<<19),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*4];
	int te=1;
	int upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return i;
		}
		int u=te;
		seg[te]=seg[i];
		te++;
		if(l>=tl&&r<=tr){
			seg[u].w+=w;
			return u;
		}
		int mid=(l+r)>>1;
		int x=upd(seg[u].cl,l,mid,tl,tr,w);
		seg[u].cl=x;
		x=upd(seg[u].cr,mid+1,r,tl,tr,w);
		seg[u].cr=x;
		seg[u].w=seg[seg[u].cl].w+seg[seg[u].cr].w;
		return u;
	}
	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;

void init(int N, int A[], int B[]) {
	n=N;
	for(int i=0;i<n;i++){
		alle.push_back(make_pair(A[i],B[i]));
		ezaf[alle[i].second].push_back(alle[i].first);
	}
	for(int i=1;i<=n;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);
//	cout<<w<<" "<<ind<<" "<<mn<<" "<<z<<" "<<unnow.back().first<<" "<<unnow.back().second<<" "<<seg.pors(dproot[unnow.back().second],0,kaf-1,unnow.back().first,ind)<<" "<<seg.pors(dproot[mn],0,kaf-1,unnow.back().first,ind)<<endl;
	if(z<w){
		w-=z;
		int f=unnow.back().second;
		unnow.pop_back();
		return upd(w,ind,f);
	}
	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);
		if(z>w){
			high=mid;
		}else{
			low=mid;
		}
	}
	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(1,n));
	for(int i=0;i<m;i++){
		unnow.push_back(make_pair(all[i]+1,all[i]-1));
		if(upd(all[i],all[i],0)==0){
			return 0;
		}
	}
	return 1;
}

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