Submission #60927

#	Time	Username	Problem	Language	Result	Execution time	Memory
60927		ngkan146	Teams (IOI15_teams)	C++11	100 / 100	2377 ms	224656 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
typedef pair<int,int> ii;
typedef pair<ii,int> iiI;
#define fi first
#define se second

struct persistentSeg{
	struct node{
		int val, Lnode, Rnode;
	};
	node seg[N * 25];
	int root[N];
	int totalNode;
	persistentSeg(){
		for(int i=1;i<=2000000;i++){
			seg[i].Lnode = 2*i;
			seg[i].Rnode = 2*i+1;
		}
		root[0] = 1;
		totalNode = 2000000;
	}
	
	int upd(int id,int l,int r,int pos,int value){
		int newNode = ++totalNode;
		seg[newNode] = seg[id];
		
		if (l == r){
			seg[newNode].val += value;
			return newNode;
		}
		
		int mid = (l+r)/2;
		
		if (pos <= mid){
			seg[newNode].Lnode = upd(seg[newNode].Lnode, l, (l+r)/2, pos, value);
		}
		else{
			seg[newNode].Rnode = upd(seg[newNode].Rnode, (l+r)/2+1, r, pos, value);
		}
		seg[newNode].val = seg[seg[newNode].Lnode].val + seg[seg[newNode].Rnode].val;
		
		return newNode;
	}
	
	int get(int id,int l,int r,int u,int v){
		if (v < l || r < u)	
			return 0;
		if (u <= l && r <= v)
			return seg[id].val;
		return get(seg[id].Lnode, l, (l+r)/2, u, v) + get(seg[id].Rnode, (l+r)/2+1, r, u, v);
	}
};

int n;
ii range[N];
persistentSeg seg;

vector <int> lis[N];

void init(int nn, int A[], int B[]) {
	n = nn;
	for(int i=0;i<n;i++){
		lis[A[i]].push_back(B[i]);
	}
	for(int i=1;i<=n;i++){
		seg.root[i] = seg.root[i-1];
		for(auto v: lis[i])
			seg.root[i] = seg.upd(seg.root[i], 1, n, v, 1);
	}
}


iiI del[500]; int delSz;

int can(int m, int lst[]) {
	//~~~~~~~~~~~~~~~~prep~~~~~~~~~~~~~~~~~~~~~~
	set <int> s;
	int tmp = 0;
	for(int i=0;i<m;i++){
		tmp = min(n+1, tmp + lst[i]);
		s.insert(lst[i]);
	}
	
	if (tmp > n)	
		return 0;
		
	int newM = 0;
	int ask[s.size()+5] = {}, askTimes[s.size()+5] = {};
	ask[0] = 0;
	for(set<int>::iterator it = s.begin(); it != s.end(); it++){
		ask[++newM] = *it;
	}
	for(int i=0;i<m;i++){
		askTimes[lower_bound(ask+1,ask+newM+1,lst[i]) - ask] ++;
	}
	//~~~~~~~~~~~~~~~solve~~~~~~~~~~~~~~~~~~~~~
	
	delSz = 0;
	del[delSz++] = iiI({{n, 0}, 0});
	
	
	for(int i=1;i<=newM;i++){
		while(delSz && del[delSz-1].fi.fi < ask[i])	delSz--;
			
		int need = ask[i] * askTimes[i];
		int last = ask[i];
		
		while(delSz){
			int current = seg.get(seg.root[ask[i]], 1, n, last, del[delSz-1].fi.fi)
						- seg.get(seg.root[del[delSz-1].fi.se], 1, n, last, del[delSz-1].fi.fi)
						+ del[delSz-1].se;
			if (need <= current)	break;
			else
				last = del[delSz-1].fi.fi+1,
				need -= current,
				delSz--;
		}
		
		if (!delSz)	return 0;
		
		int moreNeed = need + (last == 1 ? 0 : seg.get(seg.root[ask[i]], 1, n, 1, last-1)
												- seg.get(seg.root[del[delSz-1].fi.se], 1, n, 1, last-1));
		
		int id1 = seg.root[ask[i]], id2 = seg.root[del[delSz-1].fi.se], L = 1, R = n;
		
		while(L !=  R){
			int mid = (L + R)/2;
			int cur = seg.seg[seg.seg[id1].Lnode].val 
					- seg.seg[seg.seg[id2].Lnode].val
					+ del[delSz-1].se * (mid >= del[delSz-1].fi.fi);
			if (cur >= moreNeed)
				id1 = seg.seg[id1].Lnode,
				id2 = seg.seg[id2].Lnode,
				R = mid;
			else
				moreNeed -= cur,
				id1 = seg.seg[id1].Rnode,
				id2 = seg.seg[id2].Rnode,
				L = mid+1;
		}
		
		//~ int L = last-1, R = del[delSz-1].fi.fi, cur;
		
		
		//~ while(L+1<R){
			//~ int mid = (L+R)/2;
			//~ cur = seg.get(seg.root[ask[i]], 1, n, last, mid)
					//~ - seg.get(seg.root[del[delSz-1].fi.se], 1, n, last, mid)
					//~ + del[delSz-1].se * (mid == del[delSz-1].fi.fi);
			//~ if (cur >= need)
				//~ R = mid;
			//~ else 
				//~ L = mid;
		//~ }
		
		int cur = seg.get(seg.root[ask[i]], 1, n, last, R)
			- seg.get(seg.root[del[delSz-1].fi.se], 1, n, last, R)
			+ del[delSz-1].se * (R == del[delSz-1].fi.fi);
		
		while(delSz && del[delSz-1].fi.fi <= R)	delSz--;
		
		del[delSz++] = iiI({ii(R, ask[i]), cur - need});
	}
	
	return 1;
}

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