oj.uz

Submission #589323

# Submission time Handle Problem Language Result Execution time Memory
589323 2022-07-04T13:02:47 Z Temmie Teams (IOI15_teams) C++17
100 / 100
 2566 ms 215876 KB 
#include "teams.h"
#include <bits/stdc++.h>

struct Seg {
	
	struct Item {
		int val = 0, l = 0, r = 0;
	};
	
	int size;
	std::vector <Item> v;
	
	Seg() : size(1), v(1, Item()) { }
	
	int update(int ind, int now, int l, int r) {
		int nv = size++;
		v.push_back(Item());
		v[nv].val = v[now].val;
		if (!(r - l - 1)) {
			v[nv].val++;
			return nv;
		}
		if (!v[now].l) {
			v[now].l = size++;
			v[now].r = size++;
			v.resize(v.size() + 2, Item());
		}
		v[nv].l = v[now].l;
		v[nv].r = v[now].r;
		int mid = (l + r) >> 1;
		if (ind < mid) {
			int j = update(ind, v[now].l, l, mid);
			v[nv].l = j;
		} else {
			int j = update(ind, v[now].r, mid, r);
			v[nv].r = j;
		}
		v[nv].val = v[v[nv].l].val + v[v[nv].r].val;
		return nv;
	}
	
	int query(int tl, int tr, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return 0;
		}
		if (l >= tl && r <= tr) {
			return v[now].val;
		}
		int mid = (l + r) >> 1;
		return
		(v[now].l ? query(tl, tr, v[now].l, l, mid) : 0)
		+
		(v[now].r ? query(tl, tr, v[now].r, mid, r) : 0);
	}
	
};

int n;
std::vector <std::pair <int, int>> a;
std::vector <int> ord, rt;
Seg seg;

void init(int N, int A[], int B[]) {
	n = N;
	a.resize(n);
	for (int i = 0; i < n; i++) {
		a[i] = { A[i], B[i] };
	}
	ord.resize(n);
	std::iota(ord.begin(), ord.end(), 0);
	std::sort(ord.begin(), ord.end(), [] (int u, int v) -> bool { return a[u] < a[v]; });
	rt.resize(n + 1, 0);
	for (int i = 1, cnt = 0; i <= n; i++) {
		rt[i] = rt[i - 1];
		while (cnt < n && i >= a[ord[cnt]].first) {
			rt[i] = seg.update(a[ord[cnt]].second, rt[i], 1, n + 1);
			cnt++;
		}
	}
}

int can(int m, int k[]) {
	std::sort(k, k + m);
	long long sum = 0;
	for (int i = 0; i < m; i++) {
		sum += k[i];
	}
	if (sum > n) {
		return false;
	}
	std::vector <std::pair <int, int>> now;
	for (int cnt, i = 0; i < m; i++) {
		cnt = i;
		for (; cnt + 1 < m && k[cnt + 1] == k[cnt]; cnt++);
		int num = cnt - i + 1;
		now.emplace_back(k[i], k[i] * num);
		i = cnt;
	}
	now.emplace_back(n + 1, 0);
	std::vector <int> running(now.size(), 0);
	for (int i = 0; i < (int) now.size(); i++) {
		int cnt = now[i].second;
		for (int j = i; j < (int) now.size() && cnt; j++) {
			int x;
			int mn = std::min(
			x = seg.query(now[j].first, now[j + 1].first, rt[now[i].first], 1, n + 1) - running[j], cnt);
			running[j] += mn;
			cnt -= mn;
		}
		if (cnt) {
			return false;
		}
	}
	return true;
}

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 28460 KB Output is correct
2 Correct 87 ms 28476 KB Output is correct
3 Correct 79 ms 28372 KB Output is correct
4 Correct 82 ms 28692 KB Output is correct
5 Correct 56 ms 28164 KB Output is correct
6 Correct 53 ms 28108 KB Output is correct
7 Correct 56 ms 28156 KB Output is correct
8 Correct 56 ms 28196 KB Output is correct
9 Correct 46 ms 28212 KB Output is correct
10 Correct 43 ms 27904 KB Output is correct
11 Correct 47 ms 27992 KB Output is correct
12 Correct 48 ms 27812 KB Output is correct
13 Correct 58 ms 28232 KB Output is correct
14 Correct 72 ms 28276 KB Output is correct
15 Correct 72 ms 28468 KB Output is correct
16 Correct 71 ms 28428 KB Output is correct
17 Correct 56 ms 28420 KB Output is correct
18 Correct 56 ms 28400 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 28432 KB Output is correct
2 Correct 95 ms 28432 KB Output is correct
3 Correct 189 ms 30572 KB Output is correct
4 Correct 102 ms 28460 KB Output is correct
5 Correct 72 ms 28340 KB Output is correct
6 Correct 72 ms 28336 KB Output is correct
7 Correct 86 ms 28352 KB Output is correct
8 Correct 72 ms 28340 KB Output is correct
9 Correct 47 ms 28268 KB Output is correct
10 Correct 45 ms 27932 KB Output is correct
11 Correct 62 ms 28132 KB Output is correct
12 Correct 804 ms 28216 KB Output is correct
13 Correct 201 ms 28476 KB Output is correct
14 Correct 158 ms 28800 KB Output is correct
15 Correct 109 ms 28552 KB Output is correct
16 Correct 91 ms 28692 KB Output is correct
17 Correct 77 ms 28640 KB Output is correct
18 Correct 69 ms 28592 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 214088 KB Output is correct
2 Correct 627 ms 213980 KB Output is correct
3 Correct 827 ms 213976 KB Output is correct
4 Correct 564 ms 213988 KB Output is correct
5 Correct 386 ms 213184 KB Output is correct
6 Correct 406 ms 213164 KB Output is correct
7 Correct 394 ms 213332 KB Output is correct
8 Correct 385 ms 213232 KB Output is correct
9 Correct 289 ms 213812 KB Output is correct
10 Correct 278 ms 211784 KB Output is correct
11 Correct 1165 ms 212392 KB Output is correct
12 Correct 2566 ms 212408 KB Output is correct
13 Correct 857 ms 213756 KB Output is correct
14 Correct 869 ms 214640 KB Output is correct
15 Correct 535 ms 215656 KB Output is correct
16 Correct 544 ms 215876 KB Output is correct
17 Correct 370 ms 215240 KB Output is correct
18 Correct 374 ms 215228 KB Output is correct