oj.uz

Submission #292549

# Submission time Handle Problem Language Result Execution time Memory
292549 2020-09-07T09:07:56 Z Monochromatic Teams (IOI15_teams) C++17
77 / 100
 4000 ms 159096 KB 
#include "teams.h"
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n;
vector<int> sweep[500005];

int rt[500005], lf[20 * 500005], rg[20 * 500005], sum[20 * 500005], sz;

void upd(int bf, int &nd, int cl, int cr, int v){
	nd = ++ sz;
	lf[nd] = lf[bf]; rg[nd] = rg[bf]; sum[nd] = sum[bf] + 1;
	if(cl == cr) return;

	if(v <= (cl + cr) / 2)
		upd(lf[bf], lf[nd], cl, (cl + cr) / 2, v);
	else
		upd(rg[bf], rg[nd], (cl + cr) / 2 + 1, cr, v);
}

int que(int nd, int cl, int cr, int ql, int qr){
	if(qr < cl || cr < ql || cl > cr) return 0;
	if(ql <= cl && cr <= qr) return sum[nd];
	return que(lf[nd], cl, (cl + cr) / 2, ql, qr) + que(rg[nd], (cl + cr) / 2 + 1, cr, ql, qr);
}

void init(int N, int A[], int B[]){
	n = N;
	for(int i = 0; i < n; i ++)
		sweep[A[i]].push_back(B[i]);

	for(int i = 1; i <= n; i ++){
		rt[i] = rt[i - 1];
		for(int x : sweep[i])
			upd(rt[i], rt[i], 1, n, x);
	}
}

int val[500005], cnt[500005], used[500005];
int can(int M, int K[]){
	// (N + M) log N
	// vector<int> cnt(n + 1, 0);
	// for(int i = 0; i < M; i ++)
	// 	cnt[K[i]] += K[i];

	// priority_queue<int, vector<int>, greater<int> > pq;
	// for(int i = 1; i <= n; i ++){
	// 	for(int x : sweep[i]) pq.push(x);
	// 	while(pq.size() && pq.top() < i) pq.pop();
	// 	if(pq.size() < cnt[i]) return 0;
	// 	for(; cnt[i] --; pq.pop());
	// }
	// return 1;

	// M^2 log N
	sort(K, K + M);
	int sum = 0, id = 0;
	for(int i = 0; i < M; i ++){
		sum += K[i];
		if(id > 0 && val[id - 1] == K[i])
			cnt[id - 1] += K[i];
		else
			val[id] = cnt[id] = K[i], id ++;
	}
	val[id] = n + 1;

	if(sum > n) return 0;
	for(int i = 0; i < id; i ++)
		used[i] = 0;

	for(int i = 0; i < id; i ++){
		int need = cnt[i];
		for(int j = i; j < id; j ++){
			int have = que(rt[val[i]], 1, n, val[j], val[j + 1] - 1) - used[j];
			int add = min(have, need);
			need -= add; used[j] += add;
			if(need <= 0) break;
		}
		if(need > 0) return 0;
	}

	return 1;
}

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:59:6: warning: declaration of 'sum' shadows a global declaration [-Wshadow]
   59 |  int sum = 0, id = 0;
      |      ^~~
teams.cpp:10:51: note: shadowed declaration is here
   10 | int rt[500005], lf[20 * 500005], rg[20 * 500005], sum[20 * 500005], sz;
      |                                                   ^~~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 36984 KB Output is correct
2 Correct 67 ms 36984 KB Output is correct
3 Correct 65 ms 36984 KB Output is correct
4 Correct 68 ms 37624 KB Output is correct
5 Correct 44 ms 35448 KB Output is correct
6 Correct 41 ms 35452 KB Output is correct
7 Correct 40 ms 35448 KB Output is correct
8 Correct 40 ms 35448 KB Output is correct
9 Correct 40 ms 34544 KB Output is correct
10 Correct 39 ms 34288 KB Output is correct
11 Correct 41 ms 35568 KB Output is correct
12 Correct 40 ms 34416 KB Output is correct
13 Correct 47 ms 36084 KB Output is correct
14 Correct 50 ms 35568 KB Output is correct
15 Correct 62 ms 36856 KB Output is correct
16 Correct 62 ms 36856 KB Output is correct
17 Correct 44 ms 36216 KB Output is correct
18 Correct 44 ms 36088 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 37752 KB Output is correct
2 Correct 125 ms 37752 KB Output is correct
3 Correct 176 ms 41080 KB Output is correct
4 Correct 70 ms 37616 KB Output is correct
5 Correct 65 ms 36216 KB Output is correct
6 Correct 66 ms 36304 KB Output is correct
7 Correct 61 ms 36216 KB Output is correct
8 Correct 70 ms 36216 KB Output is correct
9 Correct 43 ms 34672 KB Output is correct
10 Correct 41 ms 34772 KB Output is correct
11 Correct 82 ms 36080 KB Output is correct
12 Correct 1317 ms 35184 KB Output is correct
13 Correct 331 ms 37108 KB Output is correct
14 Correct 209 ms 39160 KB Output is correct
15 Correct 95 ms 37628 KB Output is correct
16 Correct 93 ms 37712 KB Output is correct
17 Correct 69 ms 36856 KB Output is correct
18 Correct 69 ms 36700 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 147064 KB Output is correct
2 Correct 592 ms 152424 KB Output is correct
3 Correct 762 ms 159096 KB Output is correct
4 Correct 461 ms 151928 KB Output is correct
5 Correct 247 ms 143480 KB Output is correct
6 Correct 248 ms 143448 KB Output is correct
7 Correct 225 ms 143352 KB Output is correct
8 Correct 244 ms 143480 KB Output is correct
9 Correct 186 ms 136808 KB Output is correct
10 Correct 186 ms 141032 KB Output is correct
11 Correct 2128 ms 142056 KB Output is correct
12 Execution timed out 4073 ms 143044 KB Time limit exceeded
13 Halted 0 ms 0 KB -