Submission #57861

#	Time	Username	Problem	Language	Result	Execution time	Memory
57861		E869120	Teams (IOI15_teams)	C++14	0 / 100	4022 ms	129016 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> V;

struct Node{
	int val,lazy,l,r;
};

class SegmentTree{
	public:
	vector<Node>G;int size_=1;
	
	void init(){
		G.resize(3600000,Node{0,1,-1,-1});
	}
	void add(int px,int py){
		int lx=0,ly=0,rx=(1<<18),ry=(1<<18),depth=0,pos=0;
		while(depth<36){
			G[pos].val++;
			if(depth<18){
				if(px<((lx+rx)>>1)){
					if(G[pos].l==-1){G[pos].l=size_;size_++;} pos=G[pos].l;
					rx=(lx+rx)>>1;
				}
				else{
					if(G[pos].r==-1){G[pos].r=size_;size_++;} pos=G[pos].r;
					lx=(lx+rx)>>1;
				}
			}
			else{
				if(py<((ly+ry)>>1)){
					if(G[pos].l==-1){G[pos].l=size_;size_++;} pos=G[pos].l;
					ry=(ly+ry)>>1;
				}
				else{
					if(G[pos].r==-1){G[pos].r=size_;size_++;} pos=G[pos].r;
					ly=(ly+ry)>>1;
				}
			}
			depth++;
		}
		G[pos].val++;
	}
	void resets(){
		reverse(V.begin(),V.end());
		for(int i=0;i<(int)V.size();i++) {
			if(V[i].second==-1) G[V[i].first].lazy=1;
			else G[V[i].first].val=V[i].second;
		}
		V.clear();
	}
	void alldel_(int px,int py,int qx,int qy,int lx,int ly,int rx,int ry,int depth,int u){
		if((qx<=lx || rx<=px) || (qy<=ly || ry<=py)) return;
		if((px<=lx && rx<=qx) && (py<=ly && ry<=qy)) {G[u].lazy=0;V.push_back(make_pair(u,-1));return;}
		
		if(depth<18){
			V.push_back(make_pair(u,G[u].val));
			G[u].val=0;
			if(G[u].l>=0){
				alldel_(px,py,qx,qy,lx,ly,(lx+rx)>>1,ry,depth+1,G[u].l);
				G[u].val+=G[G[u].l].val*G[G[u].l].lazy;
			}
			if(G[u].r>=0){
				alldel_(px,py,qx,qy,(lx+rx)>>1,ly,rx,ry,depth+1,G[u].r);
				G[u].val+=G[G[u].r].val*G[G[u].r].lazy;
			}
		}
		else{
			V.push_back(make_pair(u,G[u].val));
			G[u].val=0;
			if(G[u].l>=0){
				alldel_(px,py,qx,qy,lx,ly,rx,(ly+ry)>>1,depth+1,G[u].l);
				G[u].val+=G[G[u].l].val*G[G[u].l].lazy;
			}
			if(G[u].r>=0){
				alldel_(px,py,qx,qy,lx,(ly+ry)>>1,rx,ry,depth+1,G[u].r);
				G[u].val+=G[G[u].r].val*G[G[u].r].lazy;
			}
		}
	}
	void alldel(int px,int py,int qx,int qy){
		qx++;qy++;
		alldel_(px,py,qx,qy,0,0,(1<<18),(1<<18),0,0);
	}
	int sum_(int px,int py,int qx,int qy,int lx,int ly,int rx,int ry,int depth,int u){
		if((qx<=lx || rx<=px) || (qy<=ly || ry<=py)) return 0;
		if((px<=lx && rx<=qx) && (py<=ly && ry<=qy)) return G[u].val;
		
		int Sum=0;
		
		if(depth<18){
			if(G[u].l>=0 && G[G[u].l].lazy==1){
				Sum += sum_(px,py,qx,qy,lx,ly,(lx+rx)>>1,ry,depth+1,G[u].l);
			}
			if(G[u].r>=0 && G[G[u].r].lazy==1){
				Sum += sum_(px,py,qx,qy,(lx+rx)>>1,ly,rx,ry,depth+1,G[u].r);
			}
		}
		else{
			if(G[u].l>=0 && G[G[u].l].lazy==1){
				Sum += sum_(px,py,qx,qy,lx,ly,rx,(ly+ry)>>1,depth+1,G[u].l);
			}
			if(G[u].r>=0 && G[G[u].r].lazy==1){
				Sum += sum_(px,py,qx,qy,lx,(ly+ry)>>1,rx,ry,depth+1,G[u].r);
			}
		}
		return Sum;
	}
	int sum(int px,int py,int qx,int qy){
		qx++;qy++;
		return sum_(px,py,qx,qy,0,0,(1<<18),(1<<18),0,0);
	}
};

int N, x[100009], y[100009];
SegmentTree X;

void init(int NN, int A[], int B[]) {
	N=NN;X.init();
	for(int i=0;i<N;i++){
		X.add(A[i], B[i]);
		x[i]=A[i]; y[i]=B[i];
	}
}

int can(int M, int K[]) {
	X.resets();
	sort(K,K+M);
	for(int i=0;i<M;i++){
		int J=X.sum(1,K[i],K[i],N);
		if(J<K[i]) return 0;
		
		int B=0;
		for(int i=17;i>=0;i--){
			int G=B+(1<<i);
			if(G<K[i]) B=G;
			else{
				int E=X.sum(1,K[i],K[i],G);
				if(E<=K[i]) B=G;
			}
		}
		int rem=K[i]; rem-=X.sum(1,K[i],K[i],B);
		X.alldel(1,K[i],K[i],B);
		
		int BB=0;
		for(int i=17;i>=0;i--){
			int G=BB+(1<<i);
			if(G>K[i]) BB+=0;
			else{
				int E=X.sum(1,B+1,BB,B+1);
				if(E<=rem) BB=G;
			}
		}
		X.alldel(1,B+1,BB,B+1);
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:136:11: warning: declaration of 'i' shadows a previous local [-Wshadow]
   for(int i=17;i>=0;i--){
           ^
teams.cpp:131:10: note: shadowed declaration is here
  for(int i=0;i<M;i++){
          ^
teams.cpp:148:11: warning: declaration of 'i' shadows a previous local [-Wshadow]
   for(int i=17;i>=0;i--){
           ^
teams.cpp:131:10: note: shadowed declaration is here
  for(int i=0;i<M;i++){
          ^

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