oj.uz

Submission #17286

# Submission time Handle Problem Language Result Execution time Memory
17286 2015-11-11T18:42:10 Z erdemkiraz Teams (IOI15_teams) C++
100 / 100
 1065 ms 330208 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 * 40];
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

# Verdict Execution time Memory Grader output
1 Correct 64 ms 320092 KB Output is correct
2 Correct 48 ms 320092 KB Output is correct
3 Correct 64 ms 320092 KB Output is correct
4 Correct 48 ms 320092 KB Output is correct
5 Correct 60 ms 320092 KB Output is correct
6 Correct 40 ms 320092 KB Output is correct
7 Correct 49 ms 320092 KB Output is correct
8 Correct 36 ms 320092 KB Output is correct
9 Correct 43 ms 320092 KB Output is correct
10 Correct 48 ms 320092 KB Output is correct
11 Correct 44 ms 320092 KB Output is correct
12 Correct 48 ms 320092 KB Output is correct
13 Correct 36 ms 320092 KB Output is correct
14 Correct 40 ms 320092 KB Output is correct
15 Correct 44 ms 320092 KB Output is correct
16 Correct 56 ms 320092 KB Output is correct
17 Correct 44 ms 320092 KB Output is correct
18 Correct 52 ms 320092 KB Output is correct
19 Correct 36 ms 320092 KB Output is correct
20 Correct 36 ms 320092 KB Output is correct
21 Correct 36 ms 320092 KB Output is correct
22 Correct 46 ms 320092 KB Output is correct
23 Correct 44 ms 320092 KB Output is correct
24 Correct 47 ms 320092 KB Output is correct
25 Correct 40 ms 320092 KB Output is correct
26 Correct 43 ms 320092 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 322416 KB Output is correct
2 Correct 113 ms 322416 KB Output is correct
3 Correct 115 ms 322416 KB Output is correct
4 Correct 109 ms 322416 KB Output is correct
5 Correct 70 ms 322416 KB Output is correct
6 Correct 56 ms 322416 KB Output is correct
7 Correct 78 ms 322416 KB Output is correct
8 Correct 80 ms 322416 KB Output is correct
9 Correct 126 ms 322416 KB Output is correct
10 Correct 82 ms 322416 KB Output is correct
11 Correct 80 ms 322416 KB Output is correct
12 Correct 93 ms 322416 KB Output is correct
13 Correct 76 ms 322416 KB Output is correct
14 Correct 94 ms 322416 KB Output is correct
15 Correct 102 ms 322416 KB Output is correct
16 Correct 75 ms 322416 KB Output is correct
17 Correct 74 ms 322416 KB Output is correct
18 Correct 92 ms 322416 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 322416 KB Output is correct
2 Correct 108 ms 322416 KB Output is correct
3 Correct 321 ms 323912 KB Output is correct
4 Correct 112 ms 322416 KB Output is correct
5 Correct 189 ms 322416 KB Output is correct
6 Correct 171 ms 322416 KB Output is correct
7 Correct 67 ms 322416 KB Output is correct
8 Correct 130 ms 322416 KB Output is correct
9 Correct 112 ms 322416 KB Output is correct
10 Correct 135 ms 322416 KB Output is correct
11 Correct 150 ms 322416 KB Output is correct
12 Correct 204 ms 322416 KB Output is correct
13 Correct 263 ms 322416 KB Output is correct
14 Correct 334 ms 322592 KB Output is correct
15 Correct 154 ms 322416 KB Output is correct
16 Correct 156 ms 322416 KB Output is correct
17 Correct 118 ms 322416 KB Output is correct
18 Correct 142 ms 322416 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 497 ms 330152 KB Output is correct
2 Correct 482 ms 330152 KB Output is correct
3 Correct 1009 ms 330208 KB Output is correct
4 Correct 477 ms 330152 KB Output is correct
5 Correct 469 ms 330152 KB Output is correct
6 Correct 450 ms 330152 KB Output is correct
7 Correct 260 ms 330152 KB Output is correct
8 Correct 403 ms 330152 KB Output is correct
9 Correct 434 ms 330152 KB Output is correct
10 Correct 391 ms 330152 KB Output is correct
11 Correct 485 ms 330152 KB Output is correct
12 Correct 636 ms 330152 KB Output is correct
13 Correct 785 ms 330152 KB Output is correct
14 Correct 1065 ms 330152 KB Output is correct
15 Correct 500 ms 330152 KB Output is correct
16 Correct 547 ms 330152 KB Output is correct
17 Correct 387 ms 330152 KB Output is correct
18 Correct 381 ms 330152 KB Output is correct