oj.uz

Submission #417707

# Submission time Handle Problem Language Result Execution time Memory
417707 2021-06-04T07:34:14 Z ja_kingy Teams (IOI15_teams) C++14
100 / 100
 1032 ms 175420 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

struct node {
	int lc, rc, cnt;
} st[1<<24];

const int mxN = 5e5+1;
int n, ncnt = 1, rts[mxN];
int upd(int x, int t, int l, int r) {
	st[ncnt] = st[t];
	t = ncnt++;
	st[t].cnt++;
	if (r - l == 1) return t; 
	int m = l+r>>1;
	if (x < m) st[t].lc = upd(x, st[t].lc, l, m);
	else st[t].rc = upd(x, st[t].rc, m, r);
	return t;
}

int merge(int x, int t, int ot, int l, int r) {
	if (x <= 0) return ot;
	if (st[t].cnt - st[ot].cnt <= x) return t;
	int nt = ncnt++;
	if (r - l == 1) {
		st[nt].cnt = x + st[ot].cnt;
		return nt;
	}
	int m = l+r>>1;
	st[nt].lc = merge(x, st[t].lc, st[ot].lc, l, m);
	st[nt].rc = merge(x-st[st[t].lc].cnt+st[st[ot].lc].cnt, st[t].rc, st[ot].rc, m, r);
	st[nt].cnt = st[st[nt].lc].cnt + st[st[nt].rc].cnt;
	return nt;
}

int get_lt(int x, int t, int ot, int l, int r) {
	if (x >= r) return st[t].cnt - st[ot].cnt;
	if (x <= l) return 0;
	int m = l+r>>1;
	return get_lt(x, st[t].lc, st[ot].lc, l, m) + get_lt(x, st[t].rc, st[ot].rc, m, r);
}

void init(int N, int A[], int B[]) {
	n = N;
	vector<pii> order;
	for (int i = 0; i < N; ++i) {
		order.push_back({A[i], B[i]});
	}
	sort(order.begin(), order.end());
	int it = 0;
	for (int i = 1; i <= N; ++i) {
		rts[i] = rts[i-1];
		while (it < N && order[it].first == i) {
			rts[i] = upd(order[it].second, rts[i], 1, N+1);
			it++;
		}
	}
}

int can(int M, int K[]) {
	sort(K, K+M);
	int rt = 0, pv = 0;
	for (int i = 0; i < M; ++i) {
		int x = K[i];
		int f = get_lt(x, rts[x], rt, 1, n+1);
		rt = merge(x+f, rts[x], rt, 1, n+1);
		if (st[rt].cnt != x+f+pv) return 0;
		pv = st[rt].cnt;
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int upd(int, int, int, int)':
teams.cpp:18:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |  int m = l+r>>1;
      |          ~^~
teams.cpp: In function 'int merge(int, int, int, int, int)':
teams.cpp:32:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int m = l+r>>1;
      |          ~^~
teams.cpp: In function 'int get_lt(int, int, int, int, int)':
teams.cpp:42:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  int m = l+r>>1;
      |          ~^~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 23040 KB Output is correct
2 Correct 64 ms 23048 KB Output is correct
3 Correct 63 ms 23120 KB Output is correct
4 Correct 65 ms 23060 KB Output is correct
5 Correct 39 ms 23068 KB Output is correct
6 Correct 45 ms 23128 KB Output is correct
7 Correct 43 ms 23128 KB Output is correct
8 Correct 39 ms 23096 KB Output is correct
9 Correct 51 ms 29720 KB Output is correct
10 Correct 40 ms 25612 KB Output is correct
11 Correct 36 ms 24120 KB Output is correct
12 Correct 36 ms 24120 KB Output is correct
13 Correct 42 ms 23332 KB Output is correct
14 Correct 51 ms 24276 KB Output is correct
15 Correct 56 ms 24284 KB Output is correct
16 Correct 55 ms 24248 KB Output is correct
17 Correct 43 ms 24552 KB Output is correct
18 Correct 43 ms 24548 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 23096 KB Output is correct
2 Correct 67 ms 23060 KB Output is correct
3 Correct 212 ms 34380 KB Output is correct
4 Correct 62 ms 23132 KB Output is correct
5 Correct 60 ms 23060 KB Output is correct
6 Correct 60 ms 23128 KB Output is correct
7 Correct 45 ms 23128 KB Output is correct
8 Correct 55 ms 23088 KB Output is correct
9 Correct 53 ms 29788 KB Output is correct
10 Correct 82 ms 42440 KB Output is correct
11 Correct 101 ms 44964 KB Output is correct
12 Correct 98 ms 44960 KB Output is correct
13 Correct 155 ms 42552 KB Output is correct
14 Correct 263 ms 39080 KB Output is correct
15 Correct 107 ms 37184 KB Output is correct
16 Correct 98 ms 37944 KB Output is correct
17 Correct 76 ms 33972 KB Output is correct
18 Correct 86 ms 38820 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 127236 KB Output is correct
2 Correct 479 ms 127316 KB Output is correct
3 Correct 1027 ms 150052 KB Output is correct
4 Correct 459 ms 127260 KB Output is correct
5 Correct 263 ms 127276 KB Output is correct
6 Correct 257 ms 127404 KB Output is correct
7 Correct 222 ms 127276 KB Output is correct
8 Correct 258 ms 127328 KB Output is correct
9 Correct 287 ms 163420 KB Output is correct
10 Correct 297 ms 174268 KB Output is correct
11 Correct 317 ms 175072 KB Output is correct
12 Correct 354 ms 175372 KB Output is correct
13 Correct 644 ms 175420 KB Output is correct
14 Correct 1032 ms 164868 KB Output is correct
15 Correct 454 ms 160104 KB Output is correct
16 Correct 451 ms 160076 KB Output is correct
17 Correct 305 ms 158568 KB Output is correct
18 Correct 303 ms 157456 KB Output is correct