oj.uz

Submission #26996

# Submission time Handle Problem Language Result Execution time Memory
26996 2017-07-08T09:57:56 Z Bruteforceman Teams (IOI15_teams) C++11
77 / 100
 1806 ms 368108 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[200010];
int W(int x, int y) {
	return count(aux[x] + 1, aux[y], aux[y]);
}
int can(int M, int K[]) {
	sort(K, K+M);
	int sum = 0;
	for(int i = 0; i < M; i++) {
		sum += K[i];
		aux[i] = K[i];
		if(sum > n) return false;
	}
	
	vector <int> s;
	for(int i = 0; i < M; i++) {
		dp[i] = count(1, K[i], K[i]) - K[i];
		while(s.size() > 1 && dp[s[s.size() - 2]] + W(s[s.size() - 2], i) <= dp[s[s.size() - 1]] + W(s[s.size() - 1], i)) {
			s.pop_back();			
		}
		if(!s.empty()) dp[i] = min(dp[i], dp[s.back()] + W(s.back(), i) - K[i]);
		while(!s.empty() && dp[s.back()] >= dp[i]) {
			s.pop_back();
		}
		s.push_back(i);
		if(dp[i] < 0) return false;
	}	
	return true;
}

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 84744 KB Output is correct
2 Correct 229 ms 84744 KB Output is correct
3 Correct 229 ms 84744 KB Output is correct
4 Correct 206 ms 85136 KB Output is correct
5 Correct 26 ms 32208 KB Output is correct
6 Correct 19 ms 32208 KB Output is correct
7 Correct 29 ms 32208 KB Output is correct
8 Correct 29 ms 32208 KB Output is correct
9 Correct 23 ms 32052 KB Output is correct
10 Correct 19 ms 31876 KB Output is correct
11 Correct 26 ms 31880 KB Output is correct
12 Correct 26 ms 32428 KB Output is correct
13 Correct 39 ms 39488 KB Output is correct
14 Correct 83 ms 49520 KB Output is correct
15 Correct 186 ms 75248 KB Output is correct
16 Correct 129 ms 75240 KB Output is correct
17 Correct 26 ms 33320 KB Output is correct
18 Correct 26 ms 33364 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 85140 KB Output is correct
2 Correct 183 ms 85140 KB Output is correct
3 Correct 336 ms 87912 KB Output is correct
4 Correct 166 ms 85136 KB Output is correct
5 Correct 43 ms 32604 KB Output is correct
6 Correct 36 ms 32604 KB Output is correct
7 Correct 33 ms 32604 KB Output is correct
8 Correct 39 ms 32604 KB Output is correct
9 Correct 13 ms 32052 KB Output is correct
10 Correct 29 ms 32216 KB Output is correct
11 Correct 29 ms 32276 KB Output is correct
12 Correct 36 ms 32824 KB Output is correct
13 Correct 139 ms 40020 KB Output is correct
14 Correct 366 ms 80160 KB Output is correct
15 Correct 189 ms 75776 KB Output is correct
16 Correct 199 ms 75768 KB Output is correct
17 Correct 63 ms 33744 KB Output is correct
18 Correct 59 ms 33768 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1626 ms 362564 KB Output is correct
2 Correct 1609 ms 362564 KB Output is correct
3 Correct 1806 ms 368108 KB Output is correct
4 Correct 1419 ms 362556 KB Output is correct
5 Correct 139 ms 63584 KB Output is correct
6 Correct 163 ms 63584 KB Output is correct
7 Correct 99 ms 63584 KB Output is correct
8 Correct 126 ms 63584 KB Output is correct
9 Correct 129 ms 62240 KB Output is correct
10 Correct 123 ms 62392 KB Output is correct
11 Correct 149 ms 62684 KB Output is correct
12 Correct 213 ms 65884 KB Output is correct
13 Correct 609 ms 105836 KB Output is correct
14 Correct 1793 ms 328268 KB Output is correct
15 Correct 1103 ms 265592 KB Output is correct
16 Incorrect 899 ms 265360 KB Output isn't correct
17 Halted 0 ms 0 KB -