oj.uz

Submission #26988

# Submission time Handle Problem Language Result Execution time Memory
26988 2017-07-08T09:00:45 Z Bruteforceman Teams (IOI15_teams) C++11
77 / 100
 4000 ms 377588 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
int n;
pii range[500010];
int dp[500010];
const int inf = 1e9;

vector <int> g[500010];

struct node {
	node *l, *r;
	int sum;
	node () {
		l = NULL;
		r = NULL;
		sum = 0;
	}
	void merge() {
		sum = 0;
		if(l) sum += l -> sum;
		if(r) sum += r -> sum;
	}
} *t[500010]; 
typedef node* pnode;

void insert(int x, pnode &cur, int b, int e) {
	if(!cur) cur = new node();
	if(b == e) {
		cur -> sum += 1;
		return ;
	}
	int m = (b + e) >> 1;
	if(x <= m) insert(x, cur -> l, b, m);
	else insert(x, cur -> r, m+1, e);
} 

void correct(pnode &cur, pnode &prev, int b, int e) {
	if(!cur) {
		cur = prev;
		return ;
	}
	if(b == e) {
		cur -> sum += prev -> sum;
		return ;
	}
	int m = (b + e) >> 1;
	correct(cur -> l, prev -> l, b, m);
	correct(cur -> r, prev -> r, m+1, e);
	cur -> merge();
}

void init(pnode &cur, int b, int e) {
	cur = new node();
	if(b == e) {
		return ;
	}
	int m = (b + e) >> 1;
	init(cur -> l, b, m);
	init(cur -> r, m+1, e);
}
int count(int x, int y, int k, pnode cur, pnode prev, int b, int e) {
	if(b == e) {
		return (cur -> sum) - (prev -> sum);
	}
	int m = (b + e) >> 1;
	if(k <= m) {
		return ((cur -> r -> sum) - (prev -> r -> sum)) + count(x, y, k, cur -> l, prev -> l, b, m);
	} else {
		return count(x, y, k, cur -> r, prev -> r, m+1, e);
	}
}
int count(int x, int y, int k) {
	if(x > y) return 0;
	return count(x, y, k, t[y], t[x-1], 1, n);
}
 
void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < n; i++) {
		range[i] = pii(A[i], B[i]);
		g[A[i]].push_back(B[i]);
	}	
	for(int i = 1; i <= n; i++) {
		sort(g[i].begin(), g[i].end());
	}
	for(int i = 0; i <= n; i++) {
		t[i] = NULL;
	}
	init(t[0], 1, n);
	for(int i = 1; i <= n; i++) {
		for(auto j : g[i]) {
			insert(j, t[i], 1, n);
		}
		correct(t[i], t[i - 1], 1, n);
	}
}
// int aux[500010];

bool bigSolver(int M, int K[]) {
	vector <pii> v;
	for(int i = 1; i <= n; i++) {
		v.push_back(pii(range[i - 1].first, -i));
		v.push_back(pii(range[i - 1].second, i));
	}
	for(int i = 0; i < M; i++) {
		v.push_back(pii(K[i], 0));
	}
	sort(v.begin(), v.end());;
	
	multiset <pii> s;
	for(auto i : v) {
		if(i.second < 0) {
			int idx = -i.second;
			s.insert(pii(range[idx - 1].second, idx));
		} else if(i.second > 0) {
			if(s.find(i) != s.end()) s.erase(s.find(i));
		} else {
			int take = 0;
			while(!s.empty() && take < i.first) {
				++take;
				s.erase(s.begin());
			}
			if(take != i.first) return false;
		}
	}
	return true;
}

const int magic = 450;

int can(int M, int K[]) {
	if(M >= magic) return bigSolver(M, K);
	
	sort(K, K+M);
	int sum = 0;
	for(int i = 0; i < M; i++) {
		sum += K[i];
		if(sum > n) return false;
	}
	for(int i = 0; i < M; i++) {
		dp[i] = count(1, K[i], K[i]) - K[i];
		for(int j = 0; j < i; j++) {
			dp[i] = min(dp[i], dp[j] + count(K[j] + 1, K[i], K[i]) - K[i]);
		}
	}	
	int ans = inf;
	for(int i = 0; i < M; i++) {
		ans = min(ans, dp[i]);
	}
	// cout << (ans >= 0) << endl;
	return (ans >= 0);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23516 KB Output is correct
2 Correct 6 ms 23516 KB Output is correct
3 Correct 3 ms 23516 KB Output is correct
4 Correct 3 ms 23516 KB Output is correct
5 Correct 3 ms 23516 KB Output is correct
6 Correct 3 ms 23792 KB Output is correct
7 Correct 3 ms 23516 KB Output is correct
8 Correct 0 ms 23516 KB Output is correct
9 Correct 0 ms 23516 KB Output is correct
10 Correct 0 ms 23516 KB Output is correct
11 Correct 3 ms 23516 KB Output is correct
12 Correct 3 ms 23516 KB Output is correct
13 Correct 3 ms 23516 KB Output is correct
14 Correct 3 ms 23516 KB Output is correct
15 Correct 6 ms 23516 KB Output is correct
16 Correct 0 ms 23516 KB Output is correct
17 Correct 3 ms 23516 KB Output is correct
18 Correct 0 ms 23516 KB Output is correct
19 Correct 0 ms 23516 KB Output is correct
20 Correct 3 ms 23516 KB Output is correct
21 Correct 3 ms 23516 KB Output is correct
22 Correct 0 ms 23516 KB Output is correct
23 Correct 0 ms 23516 KB Output is correct
24 Correct 0 ms 23516 KB Output is correct
25 Correct 3 ms 23516 KB Output is correct
26 Correct 0 ms 23516 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 83964 KB Output is correct
2 Correct 219 ms 83964 KB Output is correct
3 Correct 216 ms 83964 KB Output is correct
4 Correct 256 ms 90552 KB Output is correct
5 Correct 19 ms 31428 KB Output is correct
6 Correct 23 ms 31428 KB Output is correct
7 Correct 33 ms 31428 KB Output is correct
8 Correct 33 ms 31428 KB Output is correct
9 Correct 66 ms 37944 KB Output is correct
10 Correct 56 ms 37892 KB Output is correct
11 Correct 56 ms 37884 KB Output is correct
12 Correct 16 ms 31648 KB Output is correct
13 Correct 39 ms 38708 KB Output is correct
14 Correct 63 ms 48740 KB Output is correct
15 Correct 173 ms 74468 KB Output is correct
16 Correct 146 ms 74460 KB Output is correct
17 Correct 29 ms 32540 KB Output is correct
18 Correct 23 ms 32584 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1206 ms 84360 KB Output is correct
2 Correct 1036 ms 84360 KB Output is correct
3 Correct 366 ms 87132 KB Output is correct
4 Correct 246 ms 90560 KB Output is correct
5 Correct 1106 ms 31824 KB Output is correct
6 Correct 956 ms 31824 KB Output is correct
7 Correct 1083 ms 31824 KB Output is correct
8 Correct 989 ms 31824 KB Output is correct
9 Correct 63 ms 37944 KB Output is correct
10 Correct 303 ms 38148 KB Output is correct
11 Correct 2336 ms 38204 KB Output is correct
12 Correct 509 ms 32044 KB Output is correct
13 Correct 229 ms 39240 KB Output is correct
14 Correct 353 ms 79380 KB Output is correct
15 Correct 233 ms 74996 KB Output is correct
16 Correct 213 ms 74988 KB Output is correct
17 Correct 109 ms 32964 KB Output is correct
18 Correct 109 ms 32988 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4000 ms 377588 KB Execution timed out
2 Halted 0 ms 0 KB -