oj.uz

Submission #16541

# Submission time Handle Problem Language Result Execution time Memory
16541 2015-08-27T14:02:38 Z gs14004 Teams (IOI15_teams) C++14
77 / 100
 4000 ms 105416 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].first + lim;
			while(pos){
				tree[pos].push_back(a[i].second);
				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){
		sx += lim;
		ex += lim;
		int ret = 0;
		while(sx < ex){
			if(sx % 2 == 1) ret += nsum(sx++, sy, ey);
			if(ex % 2 == 0) ret += nsum(ex--, sy, ey);
			sx >>= 1;
			ex >>= 1;
		}
		if(sx == ex) ret += nsum(sx, sy, ey);
		return ret;
	}
}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,[&](const pi &a, const pi &b){return a.second < b.second;});
	rtree.init(n);
	sort(a,a+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 = st, e = ed;
		while(s != e){
			int m = (s + e) / 2;
			int val = rtree.query(sx.top() + 1, K[i], st+1, m);
			if(val < sum) s = m+1;
			else e = m;
		}
		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 30108 KB Output is correct
2 Correct 0 ms 30108 KB Output is correct
3 Correct 5 ms 30108 KB Output is correct
4 Correct 6 ms 30108 KB Output is correct
5 Correct 0 ms 30108 KB Output is correct
6 Correct 3 ms 30108 KB Output is correct
7 Correct 10 ms 30108 KB Output is correct
8 Correct 0 ms 30108 KB Output is correct
9 Correct 3 ms 30108 KB Output is correct
10 Correct 3 ms 30108 KB Output is correct
11 Correct 9 ms 30108 KB Output is correct
12 Correct 6 ms 30108 KB Output is correct
13 Correct 10 ms 30108 KB Output is correct
14 Correct 10 ms 30108 KB Output is correct
15 Correct 3 ms 30108 KB Output is correct
16 Correct 3 ms 30108 KB Output is correct
17 Correct 0 ms 30108 KB Output is correct
18 Correct 7 ms 30108 KB Output is correct
19 Correct 0 ms 30108 KB Output is correct
20 Correct 4 ms 30108 KB Output is correct
21 Correct 0 ms 30108 KB Output is correct
22 Correct 6 ms 30108 KB Output is correct
23 Correct 0 ms 30108 KB Output is correct
24 Correct 3 ms 30108 KB Output is correct
25 Correct 9 ms 30108 KB Output is correct
26 Correct 3 ms 30108 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 43312 KB Output is correct
2 Correct 109 ms 43312 KB Output is correct
3 Correct 131 ms 43312 KB Output is correct
4 Correct 128 ms 43704 KB Output is correct
5 Correct 50 ms 41020 KB Output is correct
6 Correct 30 ms 41020 KB Output is correct
7 Correct 24 ms 41020 KB Output is correct
8 Correct 21 ms 41020 KB Output is correct
9 Correct 55 ms 40440 KB Output is correct
10 Correct 46 ms 40452 KB Output is correct
11 Correct 41 ms 40944 KB Output is correct
12 Correct 47 ms 41112 KB Output is correct
13 Correct 52 ms 42068 KB Output is correct
14 Correct 71 ms 44564 KB Output is correct
15 Correct 103 ms 43440 KB Output is correct
16 Correct 105 ms 43200 KB Output is correct
17 Correct 37 ms 41324 KB Output is correct
18 Correct 20 ms 41160 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 43668 KB Output is correct
2 Correct 135 ms 43668 KB Output is correct
3 Correct 1832 ms 46308 KB Output is correct
4 Correct 121 ms 43664 KB Output is correct
5 Correct 1008 ms 41028 KB Output is correct
6 Correct 852 ms 41028 KB Output is correct
7 Correct 48 ms 41028 KB Output is correct
8 Correct 671 ms 41028 KB Output is correct
9 Correct 39 ms 40440 KB Output is correct
10 Correct 41 ms 40552 KB Output is correct
11 Correct 83 ms 40716 KB Output is correct
12 Correct 156 ms 41716 KB Output is correct
13 Correct 1036 ms 41740 KB Output is correct
14 Correct 2648 ms 45244 KB Output is correct
15 Correct 491 ms 43780 KB Output is correct
16 Correct 494 ms 43784 KB Output is correct
17 Correct 414 ms 41568 KB Output is correct
18 Correct 327 ms 41640 KB Output is correct

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 821 ms 101060 KB Output is correct
2 Correct 850 ms 101060 KB Output is correct
3 Execution timed out 4000 ms 105416 KB Program timed out
4 Halted 0 ms 0 KB -