oj.uz

Submission #60927

# Submission time Handle Problem Language Result Execution time Memory
60927 2018-07-25T02:18:32 Z ngkan146 Teams (IOI15_teams) C++11
100 / 100
 2377 ms 224656 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35576 KB Output is correct
2 Correct 29 ms 35656 KB Output is correct
3 Correct 39 ms 35764 KB Output is correct
4 Correct 40 ms 35764 KB Output is correct
5 Correct 38 ms 35764 KB Output is correct
6 Correct 37 ms 35764 KB Output is correct
7 Correct 37 ms 35776 KB Output is correct
8 Correct 40 ms 35828 KB Output is correct
9 Correct 39 ms 35828 KB Output is correct
10 Correct 42 ms 35828 KB Output is correct
11 Correct 29 ms 35828 KB Output is correct
12 Correct 38 ms 35828 KB Output is correct
13 Correct 30 ms 35828 KB Output is correct
14 Correct 40 ms 35828 KB Output is correct
15 Correct 35 ms 35828 KB Output is correct
16 Correct 31 ms 35828 KB Output is correct
17 Correct 36 ms 35828 KB Output is correct
18 Correct 35 ms 35828 KB Output is correct
19 Correct 34 ms 35828 KB Output is correct
20 Correct 36 ms 35828 KB Output is correct
21 Correct 32 ms 35832 KB Output is correct
22 Correct 30 ms 35832 KB Output is correct
23 Correct 37 ms 35832 KB Output is correct
24 Correct 33 ms 35832 KB Output is correct
25 Correct 32 ms 35832 KB Output is correct
26 Correct 32 ms 35832 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 59556 KB Output is correct
2 Correct 169 ms 59556 KB Output is correct
3 Correct 159 ms 59576 KB Output is correct
4 Correct 155 ms 59908 KB Output is correct
5 Correct 63 ms 59908 KB Output is correct
6 Correct 84 ms 59908 KB Output is correct
7 Correct 71 ms 59908 KB Output is correct
8 Correct 72 ms 59908 KB Output is correct
9 Correct 79 ms 59908 KB Output is correct
10 Correct 80 ms 59908 KB Output is correct
11 Correct 77 ms 59908 KB Output is correct
12 Correct 75 ms 59908 KB Output is correct
13 Correct 93 ms 59908 KB Output is correct
14 Correct 92 ms 59908 KB Output is correct
15 Correct 124 ms 59908 KB Output is correct
16 Correct 145 ms 59908 KB Output is correct
17 Correct 68 ms 59908 KB Output is correct
18 Correct 68 ms 59908 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 59972 KB Output is correct
2 Correct 182 ms 59972 KB Output is correct
3 Correct 619 ms 63000 KB Output is correct
4 Correct 165 ms 63000 KB Output is correct
5 Correct 217 ms 63000 KB Output is correct
6 Correct 213 ms 63000 KB Output is correct
7 Correct 96 ms 63000 KB Output is correct
8 Correct 164 ms 63000 KB Output is correct
9 Correct 64 ms 63000 KB Output is correct
10 Correct 78 ms 63000 KB Output is correct
11 Correct 97 ms 63000 KB Output is correct
12 Correct 235 ms 63000 KB Output is correct
13 Correct 407 ms 63000 KB Output is correct
14 Correct 677 ms 63000 KB Output is correct
15 Correct 264 ms 63000 KB Output is correct
16 Correct 200 ms 63000 KB Output is correct
17 Correct 143 ms 63000 KB Output is correct
18 Correct 146 ms 63000 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1010 ms 168800 KB Output is correct
2 Correct 1027 ms 168800 KB Output is correct
3 Correct 2247 ms 174460 KB Output is correct
4 Correct 978 ms 174460 KB Output is correct
5 Correct 651 ms 174460 KB Output is correct
6 Correct 581 ms 174460 KB Output is correct
7 Correct 332 ms 174460 KB Output is correct
8 Correct 544 ms 174460 KB Output is correct
9 Correct 264 ms 174460 KB Output is correct
10 Correct 283 ms 174480 KB Output is correct
11 Correct 367 ms 178132 KB Output is correct
12 Correct 700 ms 182908 KB Output is correct
13 Correct 1345 ms 190552 KB Output is correct
14 Correct 2377 ms 204480 KB Output is correct
15 Correct 946 ms 209184 KB Output is correct
16 Correct 917 ms 216424 KB Output is correct
17 Correct 452 ms 218176 KB Output is correct
18 Correct 433 ms 224656 KB Output is correct