oj.uz

답안 #17285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17285 2015-11-11T18:41:25 Z erdemkiraz 팀들 (IOI15_teams) C++
77 / 100
 309 ms 167660 KB 
#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

#include "teams.h"

const int N = 5e5 + 5;

ii a[N];

class node{ public:
	int x, l, r, lazy;
	node() {
		x = l = r = lazy = 0;
	}
};

node t[N * 20];
int del, ps[N];

int cnt = 1;

int insert(int x, int l, int r, int x1) {
	int nw = cnt++;
	if(l == r) {
		t[nw].x = 1;
		return nw;
	}
	int m = l + r >> 1;
	if(x1 <= m) {
		t[nw].l = insert(t[x].l, l, m, x1);
		t[nw].r = t[x].r;
	}
	else {
		t[nw].l = t[x].l;
		t[nw].r = insert(t[x].r, m + 1, r, x1);
	}
	t[nw].x = t[t[nw].l].x + t[t[nw].r].x;
	return nw;
}

int n;

void init(int x, int l, int r) {
	if(l == r)
		return;
	int m = l + r >> 1;
	t[x].l = cnt++;
	t[x].r = cnt++;
	init(t[x].l, l, m);
	init(t[x].r, m + 1, r);
}

void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 1; i <= n; i++) {
		a[i] = ii(B[i - 1], A[i - 1]);
	}
	sort(a + 1, a + n + 1);
	vector < ii > vs;
	for(int i = 1; i <= n; i++)
		vs.push_back(ii(a[i].second, i));
	sort(vs.begin(), vs.end());
	int ptr = 0;
	ps[0] = cnt++;
	init(ps[0], 1, n);
	for(int i = 1; i <= n; i++) {
		ps[i] = ps[i - 1];
		//printf("vs = %d ", i);
		while(ptr < vs.size() and vs[ptr].first <= i) {
			//printf("%d ", vs[ptr].second);
			ps[i] = insert(ps[i], 1, n, vs[ptr].second);
			ptr++;
		}
		//puts("");
	}
	del = cnt++;
	init(del, 1, n);
}

void push(int x) {
	if(t[x].lazy) {
		t[t[x].l].x = t[t[t[x].lazy].l].x;
		t[t[x].r].x = t[t[t[x].lazy].r].x;
		t[t[x].l].lazy = t[t[x].lazy].l;
		t[t[x].r].lazy = t[t[x].lazy].r;
		t[x].lazy = 0;
	}
}

int get(int x, int del, int l, int r, int x1, int x2, int k) {
	if(x1 <= l and r <= x2 and t[x].x - t[del].x <= k) {
		t[del].lazy = x;
		int ret = t[x].x - t[del].x;
		t[del].x += ret;
		return ret;
	}
	if(x2 < l or r < x1 or l == r)
		return 0;
    int m = l + r >> 1;
    push(del);
    int lf = get(t[x].l, t[del].l, l, m, x1, x2, k);
    if(lf == k) {
		t[del].x = t[t[del].l].x + t[t[del].r].x;
		return k;
	}
	k -= lf;
	int rf = get(t[x].r, t[del].r, m + 1, r, x1, x2, k);
	t[del].x = t[t[del].l].x + t[t[del].r].x;
	return lf + rf;
}

void clear(int x) {
	if(t[x].x and t[x].l)
		clear(t[x].l);
	if(t[x].x and t[x].r)
		clear(t[x].r);
	t[x].x = t[x].lazy = 0;
}

int can(int M, int K[]) {
	sort(K, K + M);
	int sum = 0;
	for(int i = 0; i < M; i++) {
		if(sum + K[i] > n)
			return 0;
		sum += K[i];
	}
	clear(del);
	for(int i = 0; i < M; i++) {
		int id = lower_bound(a + 1, a + n + 1, ii(K[i], 0)) - a;
		//printf("id = %d ", id);
		int res = get(ps[K[i]], del, 1, n, id, n, K[i]);
		//printf("res = %d\n", res);
		if(res != K[i])
			return 0;
	}
	return 1;
}

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 166164 KB Output is correct
2 Correct 88 ms 166164 KB Output is correct
3 Correct 86 ms 166164 KB Output is correct
4 Correct 95 ms 166164 KB Output is correct
5 Correct 62 ms 166164 KB Output is correct
6 Correct 57 ms 166164 KB Output is correct
7 Correct 52 ms 166164 KB Output is correct
8 Correct 49 ms 166164 KB Output is correct
9 Correct 107 ms 166164 KB Output is correct
10 Correct 63 ms 166164 KB Output is correct
11 Correct 44 ms 166164 KB Output is correct
12 Correct 58 ms 166164 KB Output is correct
13 Correct 64 ms 166164 KB Output is correct
14 Correct 62 ms 166164 KB Output is correct
15 Correct 72 ms 166164 KB Output is correct
16 Correct 83 ms 166164 KB Output is correct
17 Correct 62 ms 166164 KB Output is correct
18 Correct 60 ms 166164 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 166164 KB Output is correct
2 Correct 88 ms 166164 KB Output is correct
3 Correct 295 ms 167660 KB Output is correct
4 Correct 83 ms 166164 KB Output is correct
5 Correct 144 ms 166164 KB Output is correct
6 Correct 152 ms 166164 KB Output is correct
7 Correct 57 ms 166164 KB Output is correct
8 Correct 126 ms 166164 KB Output is correct
9 Correct 112 ms 166164 KB Output is correct
10 Correct 113 ms 166164 KB Output is correct
11 Correct 137 ms 166164 KB Output is correct
12 Correct 189 ms 166164 KB Output is correct
13 Correct 229 ms 166164 KB Output is correct
14 Correct 309 ms 166340 KB Output is correct
15 Correct 147 ms 166164 KB Output is correct
16 Correct 141 ms 166164 KB Output is correct
17 Correct 110 ms 166164 KB Output is correct
18 Correct 127 ms 166164 KB Output is correct

Subtask #4
0.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 0 KB -1: Interrupted system call
2 Halted 0 ms 0 KB -