oj.uz

Submission #16550

# Submission time Handle Problem Language Result Execution time Memory
16550 2015-08-27T14:24:13 Z gs14004 Teams (IOI15_teams) C++14
100 / 100
 2700 ms 107508 KB 
#include "teams.h"
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
typedef pair<int,int> pi;

int n;
pi a[500005];

struct rtree{
	int lim;
	vector<int> tree[1050000];
	void init(int n){
		for(lim = 1; lim <= n; lim <<= 1);
		for(int i=0; i<n; i++){
			int pos = a[i].second + lim;
			while(pos){
				tree[pos].push_back(a[i].first);
				pos >>= 1;
			}
		}
	}
	int nsum(int idx, int s, int e){
		return (int)(upper_bound(tree[idx].begin(), tree[idx].end(), e) - lower_bound(tree[idx].begin(), tree[idx].end(), s));
	}
	int query(int sx, int ex, int sy, int ey){
		sy += lim;
		ey += lim;
		int ret = 0;
		while(sy < ey){
			if(sy % 2 == 1) ret += nsum(sy++, sx, ex);
			if(ey % 2 == 0) ret += nsum(ey--, sx, ex);
			sy >>= 1;
			ey >>= 1;
		}
		if(sy == ey) ret += nsum(sy, sx, ex);
		return ret;
	}
	int kth(int sx, int ex, int cnt){
		int pos = 1;
		while(pos < lim){
			int tmp = nsum(2 * pos, sx, ex);
			if(cnt <= tmp){
				pos *= 2;
			}
			else{
				cnt -= tmp;
				pos = pos * 2 + 1;
			}
		}
		return pos - lim;
	}
}rtree;

void init(int N, int A[], int B[]) {
	n = N;
	for(int i=0; i<N; i++){
		a[i] = pi(A[i], B[i]);
	}
	sort(a,a+n);
	rtree.init(n);
}

stack<int> sx, sy, cnt;

int can(int M, int K[]) {
	while(!sx.empty()){
		sx.pop();
		sy.pop();
		cnt.pop();
	}
	sort(K, K+M);
	sx.push(0);
	sy.push(n);
	cnt.push(0);
	for(int i=0; i<M; i++){
		while(!sy.empty() && sy.top() < K[i]){
			sx.pop();
			sy.pop();
			cnt.pop();
		}
		int sum = K[i], st = K[i] - 1, ed = -1;
		while(!sx.empty()){
			int minus = rtree.query(sx.top() + 1, K[i], st + 1, sy.top()) + cnt.top();
			if(sum > minus) sum -= minus;
			else{
				ed = sy.top();
				break;
			}
			st = sy.top();
			sx.pop();
			sy.pop();
			cnt.pop();
		}
		if(ed == -1) return 0; 
		int s = rtree.kth(sx.top() + 1, K[i], sum + rtree.query(sx.top() + 1, K[i], 0, st)); // Lower bound
		s = min(s, ed);    
		int tmp  = rtree.query(sx.top() + 1, K[i], st + 1, s) - sum;
		sx.push(K[i]);
		sy.push(s);
		cnt.push(tmp);
	}
	return 1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 30104 KB Output is correct
2 Correct 0 ms 30104 KB Output is correct
3 Correct 5 ms 30104 KB Output is correct
4 Correct 5 ms 30104 KB Output is correct
5 Correct 3 ms 30104 KB Output is correct
6 Correct 7 ms 30104 KB Output is correct
7 Correct 10 ms 30104 KB Output is correct
8 Correct 3 ms 30104 KB Output is correct
9 Correct 0 ms 30104 KB Output is correct
10 Correct 5 ms 30104 KB Output is correct
11 Correct 0 ms 30104 KB Output is correct
12 Correct 0 ms 30104 KB Output is correct
13 Correct 10 ms 30104 KB Output is correct
14 Correct 3 ms 30104 KB Output is correct
15 Correct 3 ms 30104 KB Output is correct
16 Correct 5 ms 30104 KB Output is correct
17 Correct 4 ms 30104 KB Output is correct
18 Correct 6 ms 30104 KB Output is correct
19 Correct 6 ms 30104 KB Output is correct
20 Correct 10 ms 30104 KB Output is correct
21 Correct 0 ms 30104 KB Output is correct
22 Correct 6 ms 30104 KB Output is correct
23 Correct 6 ms 30104 KB Output is correct
24 Correct 6 ms 30104 KB Output is correct
25 Correct 6 ms 30104 KB Output is correct
26 Correct 3 ms 30104 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 43044 KB Output is correct
2 Correct 107 ms 43044 KB Output is correct
3 Correct 117 ms 43044 KB Output is correct
4 Correct 115 ms 43436 KB Output is correct
5 Correct 37 ms 41016 KB Output is correct
6 Correct 29 ms 41016 KB Output is correct
7 Correct 19 ms 41016 KB Output is correct
8 Correct 44 ms 41016 KB Output is correct
9 Correct 57 ms 40692 KB Output is correct
10 Correct 56 ms 40692 KB Output is correct
11 Correct 51 ms 40692 KB Output is correct
12 Correct 22 ms 40464 KB Output is correct
13 Correct 37 ms 42308 KB Output is correct
14 Correct 62 ms 45264 KB Output is correct
15 Correct 96 ms 43236 KB Output is correct
16 Correct 105 ms 43164 KB Output is correct
17 Correct 34 ms 40448 KB Output is correct
18 Correct 31 ms 39912 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 43524 KB Output is correct
2 Correct 138 ms 43524 KB Output is correct
3 Correct 566 ms 46164 KB Output is correct
4 Correct 118 ms 43520 KB Output is correct
5 Correct 309 ms 41024 KB Output is correct
6 Correct 266 ms 41024 KB Output is correct
7 Correct 42 ms 41024 KB Output is correct
8 Correct 210 ms 41024 KB Output is correct
9 Correct 58 ms 40692 KB Output is correct
10 Correct 75 ms 40692 KB Output is correct
11 Correct 80 ms 40692 KB Output is correct
12 Correct 136 ms 40468 KB Output is correct
13 Correct 454 ms 41980 KB Output is correct
14 Correct 745 ms 45076 KB Output is correct
15 Correct 253 ms 43784 KB Output is correct
16 Correct 236 ms 43856 KB Output is correct
17 Correct 275 ms 40968 KB Output is correct
18 Correct 193 ms 40900 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 102228 KB Output is correct
2 Correct 841 ms 102228 KB Output is correct
3 Correct 2236 ms 107508 KB Output is correct
4 Correct 826 ms 102328 KB Output is correct
5 Correct 1039 ms 82276 KB Output is correct
6 Correct 984 ms 82144 KB Output is correct
7 Correct 184 ms 82276 KB Output is correct
8 Correct 768 ms 82144 KB Output is correct
9 Correct 280 ms 76084 KB Output is correct
10 Correct 265 ms 76084 KB Output is correct
11 Correct 303 ms 76084 KB Output is correct
12 Correct 415 ms 76228 KB Output is correct
13 Correct 1442 ms 84044 KB Output is correct
14 Correct 2700 ms 105120 KB Output is correct
15 Correct 1130 ms 100260 KB Output is correct
16 Correct 1101 ms 102748 KB Output is correct
17 Correct 744 ms 95136 KB Output is correct
18 Correct 657 ms 92176 KB Output is correct