oj.uz

Submission #17284

# Submission time Handle Problem Language Result Execution time Memory
17284 2015-11-11T18:15:59 Z erdemkiraz Teams (IOI15_teams) C++
77 / 100
 988 ms 524288 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;
	node *l, *r, *lazy;
	node() {
		x = 0;
		l = r = lazy = 0;
	}
};

typedef node* pNode;

pNode del;
pNode t[N];

pNode insert(pNode x, int l, int r, int x1) {
	pNode nw = new node;
	if(l == r) {
		nw -> x = 1;
		return nw;
	}
	int m = l + r >> 1;
	if(x1 <= m) {
		nw -> l = insert(x -> l, l, m, x1);
		nw -> r = x -> r;
	}
	else {
		nw -> l = x -> l;
		nw -> r = insert(x -> r, m + 1, r, x1);
	}
	nw -> x = nw -> l -> x + nw -> r -> x;
	return nw;
}

int n;

void init(pNode x, int l, int r) {
	if(l == r)
		return;
	int m = l + r >> 1;
	x -> l = new node;
	x -> r = new node;
	init(x -> l, l, m);
	init(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;
	t[0] = new node;
	init(t[0], 1, n);
	for(int i = 1; i <= n; i++) {
		t[i] = t[i - 1];
		//printf("vs = %d ", i);
		while(ptr < vs.size() and vs[ptr].first <= i) {
			//printf("%d ", vs[ptr].second);
			t[i] = insert(t[i], 1, n, vs[ptr].second);
			ptr++;
		}
		//puts("");
	}
	del = new node;
	init(del, 1, n);
}

void push(pNode x, pNode del) {
	if(del -> lazy) {
		del -> l -> x = del -> lazy -> l -> x;
		del -> r -> x = del -> lazy -> r -> x;
		del -> l -> lazy = del -> lazy -> l;
		del -> r -> lazy = del -> lazy -> r;
		del -> lazy = 0;
	}
}

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

void clear(pNode x) {
	if(x -> x and x -> l)
		clear(x -> l);
	if(x -> x and x -> r)
		clear(x -> r);
	x -> lazy = 0;
	x -> x = 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(t[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 0 ms 9544 KB Output is correct
2 Correct 0 ms 9544 KB Output is correct
3 Correct 2 ms 9544 KB Output is correct
4 Correct 0 ms 9544 KB Output is correct
5 Correct 0 ms 9544 KB Output is correct
6 Correct 0 ms 9544 KB Output is correct
7 Correct 0 ms 9544 KB Output is correct
8 Correct 0 ms 9544 KB Output is correct
9 Correct 2 ms 9544 KB Output is correct
10 Correct 0 ms 9544 KB Output is correct
11 Correct 0 ms 9544 KB Output is correct
12 Correct 0 ms 9544 KB Output is correct
13 Correct 2 ms 9544 KB Output is correct
14 Correct 2 ms 9544 KB Output is correct
15 Correct 2 ms 9544 KB Output is correct
16 Correct 0 ms 9544 KB Output is correct
17 Correct 0 ms 9544 KB Output is correct
18 Correct 0 ms 9544 KB Output is correct
19 Correct 0 ms 9544 KB Output is correct
20 Correct 2 ms 9544 KB Output is correct
21 Correct 0 ms 9544 KB Output is correct
22 Correct 2 ms 9544 KB Output is correct
23 Correct 0 ms 9544 KB Output is correct
24 Correct 0 ms 9544 KB Output is correct
25 Correct 0 ms 9544 KB Output is correct
26 Correct 0 ms 9544 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 112992 KB Output is correct
2 Correct 162 ms 112992 KB Output is correct
3 Correct 172 ms 112992 KB Output is correct
4 Correct 153 ms 112992 KB Output is correct
5 Correct 118 ms 112992 KB Output is correct
6 Correct 71 ms 112992 KB Output is correct
7 Correct 89 ms 112992 KB Output is correct
8 Correct 117 ms 112992 KB Output is correct
9 Correct 130 ms 112992 KB Output is correct
10 Correct 129 ms 112992 KB Output is correct
11 Correct 86 ms 112992 KB Output is correct
12 Correct 128 ms 112992 KB Output is correct
13 Correct 86 ms 112992 KB Output is correct
14 Correct 144 ms 112992 KB Output is correct
15 Correct 159 ms 112992 KB Output is correct
16 Correct 143 ms 112992 KB Output is correct
17 Correct 110 ms 112992 KB Output is correct
18 Correct 104 ms 112992 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 112992 KB Output is correct
2 Correct 185 ms 112992 KB Output is correct
3 Correct 424 ms 115004 KB Output is correct
4 Correct 167 ms 112992 KB Output is correct
5 Correct 241 ms 112992 KB Output is correct
6 Correct 223 ms 112992 KB Output is correct
7 Correct 136 ms 112992 KB Output is correct
8 Correct 211 ms 112992 KB Output is correct
9 Correct 150 ms 112992 KB Output is correct
10 Correct 180 ms 112992 KB Output is correct
11 Correct 191 ms 112992 KB Output is correct
12 Correct 250 ms 112992 KB Output is correct
13 Correct 329 ms 112992 KB Output is correct
14 Correct 445 ms 113816 KB Output is correct
15 Correct 198 ms 112992 KB Output is correct
16 Correct 227 ms 112992 KB Output is correct
17 Correct 176 ms 112992 KB Output is correct
18 Correct 201 ms 112992 KB Output is correct

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 988 ms 524288 KB Memory limit exceeded
2 Halted 0 ms 0 KB -