Submission #59557

#	Time	Username	Problem	Language	Result	Execution time	Memory
59557		ngkan146	Teams (IOI15_teams)	C++11	0 / 100	4057 ms	163728 KiB

teams

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

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

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

vector <int> lis[500005];

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);
	}
	//~ for(int i=1;i<=n;i++){
		//~ cerr << "root " << i << endl;
		//~ for(int j=1;j<=n;j++)
			//~ cerr << seg.get(seg.root[i], 1, n, j, j) << ' '; 	cerr << endl;
	//~ }
}

int currentInRange(int curRootId,int L,int R, const vector<ii> &del){
	int res = 0, cur = L;
	for(int i=0;cur <= R; i++){
		//cerr << cur << ' ' << min(del[i].fi-1, R) << ' ' << del[i].se << endl;
		if (cur <= min(del[i].fi, R))
		res += seg.get(seg.root[curRootId], 1, n, cur, min(del[i].fi, R))
			 - seg.get(seg.root[del[i].se], 1, n, cur, min(del[i].fi, R));
		//cerr << res << endl;
		cur = max(cur, del[i].fi+1);
		if (cur > R)	break;
	}
	return res;
}

int can(int m, int lst[]) {
	//~~~~~~~~~~~~~~~~prep~~~~~~~~~~~~~~~~~~~~~~
	set <int> s;
	int tmp = 0;
	for(int i=0;i<m && tmp <= n;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] = {};
	
	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] ++;
	}
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	
	//cerr << "start asking" << endl;
	vector <ii> del;
	del.push_back({n, 0});
	
	for(int i=1;i<=newM;i++){	
		while(del.size() && del[0].fi < ask[i])	del.erase(del.begin());
		
		//~ for(auto v: del){
			//~ cerr << v.fi << ' ' << v.se << ' ';
		//~ }cerr << endl;
		
		int L = ask[i]-1, R = n, curRes = -1;
		while(L+1<R){
			int mid = (L+R)/2;
			if (currentInRange(ask[i], ask[i], mid, del) < ask[i] * askTimes[i])
				L = mid;
			else
				R = mid;
		}
		curRes = currentInRange(ask[i], ask[i], R, del);
		
		//~ cerr << "ask " << ask[i] << " " << askTimes[i] << ' ' << curRes << " ////// " << seg.get(seg.root[ask[i]],1,n,1,n) << endl;
		if (curRes < ask[i] * askTimes[i]){
			//~ cerr << 0 << " can't here: " << ask[i] << ' ' << askTimes[i] << endl;
			return 0;
		}
		while(del.size() && del[0].fi <= R)	del.erase(del.begin());
		del.insert(del.begin(), {R, ask[i]});
	}
	
	//~ cerr << "1\n";
	return 1;
}

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