oj.uz

답안 #16549

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16549 2015-08-27T14:23:43 Z gs14004 팀들 (IOI15_teams) C++14
77 / 100
 4000 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 st = 0, ed = n;
		while(st != ed){
			int m = (st + ed) / 2;
			if(query(sx, ex, 0, m) < cnt) st = m+1;
			else ed = m;
		}
		return st;
		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 = max(s, st);
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 30104 KB Output is correct
2 Correct 3 ms 30104 KB Output is correct
3 Correct 5 ms 30104 KB Output is correct
4 Correct 6 ms 30104 KB Output is correct
5 Correct 6 ms 30104 KB Output is correct
6 Correct 6 ms 30104 KB Output is correct
7 Correct 3 ms 30104 KB Output is correct
8 Correct 10 ms 30104 KB Output is correct
9 Correct 6 ms 30104 KB Output is correct
10 Correct 7 ms 30104 KB Output is correct
11 Correct 6 ms 30104 KB Output is correct
12 Correct 3 ms 30104 KB Output is correct
13 Correct 7 ms 30104 KB Output is correct
14 Correct 3 ms 30104 KB Output is correct
15 Correct 6 ms 30104 KB Output is correct
16 Correct 3 ms 30104 KB Output is correct
17 Correct 6 ms 30104 KB Output is correct
18 Correct 6 ms 30104 KB Output is correct
19 Correct 9 ms 30104 KB Output is correct
20 Correct 4 ms 30104 KB Output is correct
21 Correct 0 ms 30104 KB Output is correct
22 Correct 10 ms 30104 KB Output is correct
23 Correct 7 ms 30104 KB Output is correct
24 Correct 3 ms 30104 KB Output is correct
25 Correct 5 ms 30104 KB Output is correct
26 Correct 3 ms 30104 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 43044 KB Output is correct
2 Correct 116 ms 43044 KB Output is correct
3 Correct 130 ms 43044 KB Output is correct
4 Correct 123 ms 43436 KB Output is correct
5 Correct 44 ms 41016 KB Output is correct
6 Correct 34 ms 41016 KB Output is correct
7 Correct 31 ms 41016 KB Output is correct
8 Correct 16 ms 41016 KB Output is correct
9 Correct 75 ms 40692 KB Output is correct
10 Correct 78 ms 40692 KB Output is correct
11 Correct 36 ms 40692 KB Output is correct
12 Correct 25 ms 40464 KB Output is correct
13 Correct 44 ms 42308 KB Output is correct
14 Correct 50 ms 45264 KB Output is correct
15 Correct 118 ms 43236 KB Output is correct
16 Correct 95 ms 43164 KB Output is correct
17 Correct 31 ms 40448 KB Output is correct
18 Correct 27 ms 39912 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 43524 KB Output is correct
2 Correct 132 ms 43524 KB Output is correct
3 Correct 1179 ms 46164 KB Output is correct
4 Correct 110 ms 43520 KB Output is correct
5 Correct 537 ms 41024 KB Output is correct
6 Correct 491 ms 41024 KB Output is correct
7 Correct 36 ms 41024 KB Output is correct
8 Correct 383 ms 41024 KB Output is correct
9 Correct 84 ms 40692 KB Output is correct
10 Correct 280 ms 40692 KB Output is correct
11 Correct 264 ms 40692 KB Output is correct
12 Correct 388 ms 40468 KB Output is correct
13 Correct 879 ms 41980 KB Output is correct
14 Correct 1561 ms 45076 KB Output is correct
15 Correct 460 ms 43784 KB Output is correct
16 Correct 440 ms 43856 KB Output is correct
17 Correct 409 ms 40968 KB Output is correct
18 Correct 416 ms 40900 KB Output is correct

Subtask #4
0.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 842 ms 102228 KB Output is correct
2 Correct 825 ms 102228 KB Output is correct
3 Execution timed out 4000 ms 107508 KB Program timed out
4 Halted 0 ms 0 KB -