Submission #287352

#	Time	Username	Problem	Language	Result	Execution time	Memory
287352		Namnamseo	Teams (IOI15_teams)	C++17	100 / 100	3328 ms	98392 KiB

teams

#include <cstdio>
#include <cstdlib>

#include <vector>
#include <stack>
#include <algorithm>
#define all(x) (x).begin(), (x).end()
#define pb push_back
using namespace std;

typedef pair<int,int> pp;
stack<pp > st;
stack<int> left;
int n;

struct seg2d{
	static const int M=524288;
	vector<int> tree[M*2];
	void addPoint(int x,int y){
		y+=M;
		while(y){
			tree[y].pb(x);
			y>>=1;
		}
	}
	void init(){
		int i;
		for(i=1;i<2*M;++i) sort(all(tree[i]));
	}
	inline int get(int point,int x,int y){
		return max(0,int(upper_bound(all(tree[point]),y) -
						 lower_bound(all(tree[point]),x)));
	}
	int query(int l,int r,int x,int y){
		int ret=0;
		x+=M; y+=M;
		while(x<=y){
			if(x==y){
				ret += get(x,l,r); break;
			}
			if(x&1)      ret+=get(x++,l,r);
			if((y&1)==0) ret+=get(y--,l,r);
			x>>=1; y>>=1;
		}
		return ret;
	}
	int get_over(int x1,int x2,int k){
		int pos=1;
		int cnt=0;
		while(pos<M){
			int l=pos*2, r=l+1;
			int tmp=get(l,x1,x2);
			if(cnt+tmp < k){
				cnt += tmp;
				pos=r;
			} else pos=l;
		}
		return pos-M;
	}
} seg;
void init(int N, int A[], int B[]) {
	int i;
	n=N;
	for(i=0;i<N;++i) seg.addPoint(A[i],B[i]);
	seg.init();
}

int can(int M, int K[]) {
	sort(K,K+M);
	int i;
	while(st  .size()) st  .pop();
	while(left.size()) left.pop();
	st.push({0,n});
	left.push(0);
	for(i=0;i<M;++i){

		int& x=K[i];
		
		int curcnt=x, lasty=x-1;
		
		for(;st.size()>1;){
			auto t=st.top();
			if(t.second < x){
				st.pop(); left.pop();
				continue;
			}
			int cnt=seg.query(t.first+1, x, lasty+1, t.second) + left.top();
			if(curcnt <= cnt) {
				break;
			}
			st.pop(); left.pop();
			lasty  = t.second;
			curcnt -= cnt;
		}
		
		pp t=st.top();
		if(seg.query(t.first+1, x, lasty+1, t.second) + left.top() < curcnt) return 0;
		
		int R=min(t.second, seg.get_over(t.first+1, x, curcnt + seg.query(t.first+1, x, 0, lasty) ));
		
		left.push(seg.query(st.top().first+1,x,lasty+1,R)-curcnt);
		st.push({x,R});
	}
	return 1;
}

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