oj.uz

답안 #16548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
16548 2015-08-27T14:22:34 Z gs14004 팀들 (IOI15_teams) C++14
0 / 100
 125 ms 45264 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 = 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
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 30104 KB Output is correct
2 Correct 6 ms 30104 KB Output is correct
3 Correct 3 ms 30104 KB Output is correct
4 Correct 10 ms 30104 KB Output is correct
5 Correct 9 ms 30104 KB Output is correct
6 Correct 10 ms 30104 KB Output is correct
7 Correct 7 ms 30104 KB Output is correct
8 Correct 5 ms 30104 KB Output is correct
9 Correct 6 ms 30104 KB Output is correct
10 Correct 10 ms 30104 KB Output is correct
11 Correct 3 ms 30104 KB Output is correct
12 Correct 11 ms 30104 KB Output is correct
13 Incorrect 3 ms 30104 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 43044 KB Output is correct
2 Correct 97 ms 43044 KB Output is correct
3 Correct 123 ms 43044 KB Output is correct
4 Correct 111 ms 43436 KB Output is correct
5 Correct 33 ms 41016 KB Output is correct
6 Correct 30 ms 41016 KB Output is correct
7 Correct 34 ms 41016 KB Output is correct
8 Correct 21 ms 41016 KB Output is correct
9 Correct 79 ms 40692 KB Output is correct
10 Correct 81 ms 40692 KB Output is correct
11 Correct 41 ms 40692 KB Output is correct
12 Correct 30 ms 40464 KB Output is correct
13 Correct 33 ms 42308 KB Output is correct
14 Correct 55 ms 45264 KB Output is correct
15 Correct 98 ms 43236 KB Output is correct
16 Incorrect 100 ms 43164 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -