oj.uz

Submission #332824

# Submission time Handle Problem Language Result Execution time Memory
332824 2020-12-03T14:01:33 Z cki86201 Teams (IOI15_teams) C++17
100 / 100
 2072 ms 153884 KB 
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

int rt[500050], tn;
int T[10000010], N;
int ch[10000010][2];
vector <int> bl[500050];

int Ins(int prt, int l, int r, int x) {
	int me = ++tn;
	T[me] = T[prt] + 1;
	ch[me][0] = ch[prt][0];
	ch[me][1] = ch[prt][1];
	if(l != r) {
		int m = (l + r) >> 1;
		if(x <= m) ch[me][0] = Ins(ch[prt][0], l, m, x);
		else ch[me][1] = Ins(ch[prt][1], m+1, r, x);
	}
	return me;
}
int read(int prt, int l, int r, int s, int e) {
	if(s <= l && r <= e) return T[prt];
	int m = (l + r) >> 1, res = 0;
	if(s <= m) res += read(ch[prt][0], l, m, s, e);
	if(m < e) res += read(ch[prt][1], m+1, r, s, e);
	return res;
}

int Read(int x, int l, int r) {
	return read(rt[x], 1, N, l, r);
}

void init(int N, int A[], int B[]) {
	::N = N;
	rt[0] = ++tn;
	for(int i=0;i<N;i++) bl[A[i]].pb(B[i]);
	for(int i=1;i<=N;i++) {
		rt[i] = rt[i-1];
		for(int r : bl[i]) {
			rt[i] = Ins(rt[i], 1, N, r);
		}
	}
}

int dp[200020];
int can(int M, int K[]) {
	sort(K, K+M, greater<>());
	vector <pii> V;
	V.pb({N+1, 0});
	for(int i=0, s=0;i<M;i++) {
		if(szz(V) && V.back().Fi == K[i]) V.back().Se += K[i];
		else V.pb({K[i], K[i]});
		s += K[i];
		if(s > N) return 0;
	}
	vector <int> iv = {0};
	vector <int> cv;
	auto mp = [&](int xi, int yi) {
		int xv = dp[xi], yv = dp[yi];
		int low = 1, high = V[yi].Fi - 1, res = 0;
		while(low <= high) {
			int mid = (low + high) >> 1;
			if(Read(mid, V[yi].Fi, V[xi].Fi - 1) < yv - xv) res = mid, low = mid + 1;
			else high = mid - 1;
		}
		return res;
	};
	for(int i=1;i<szz(V);i++) {
		auto [x, cnt] = V[i];
		while(szz(cv) && cv.back() >= x) cv.pop_back(), iv.pop_back();
		int j = iv.back();
		dp[i] = dp[j] + Read(x, x, V[j].Fi - 1) - cnt;
		if(dp[i] < 0) return 0;
		while(szz(iv) && dp[i] < dp[iv.back()]) iv.pop_back(), cv.pop_back();
		int p = mp(iv.back(), i);
		while(szz(cv) && cv.back() >= p) {
			iv.pop_back(); cv.pop_back();
			p = mp(iv.back(), i);
		}
		iv.pb(i);
		cv.pb(p);
	}
	return 1;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:45:34: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   45 | void init(int N, int A[], int B[]) {
      |                                  ^
teams.cpp:17:18: note: shadowed declaration is here
   17 | int T[10000010], N;
      |                  ^

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 35864 KB Output is correct
2 Correct 81 ms 35948 KB Output is correct
3 Correct 78 ms 35820 KB Output is correct
4 Correct 79 ms 36204 KB Output is correct
5 Correct 45 ms 34796 KB Output is correct
6 Correct 40 ms 34796 KB Output is correct
7 Correct 40 ms 34796 KB Output is correct
8 Correct 41 ms 34796 KB Output is correct
9 Correct 38 ms 33764 KB Output is correct
10 Correct 37 ms 33764 KB Output is correct
11 Correct 40 ms 34916 KB Output is correct
12 Correct 38 ms 33764 KB Output is correct
13 Correct 47 ms 35048 KB Output is correct
14 Correct 53 ms 34532 KB Output is correct
15 Correct 74 ms 35692 KB Output is correct
16 Correct 70 ms 35692 KB Output is correct
17 Correct 44 ms 34948 KB Output is correct
18 Correct 43 ms 35052 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 36204 KB Output is correct
2 Correct 88 ms 36204 KB Output is correct
3 Correct 397 ms 39276 KB Output is correct
4 Correct 83 ms 36204 KB Output is correct
5 Correct 199 ms 35180 KB Output is correct
6 Correct 131 ms 35244 KB Output is correct
7 Correct 198 ms 35180 KB Output is correct
8 Correct 141 ms 35180 KB Output is correct
9 Correct 38 ms 33764 KB Output is correct
10 Correct 41 ms 34020 KB Output is correct
11 Correct 48 ms 35172 KB Output is correct
12 Correct 134 ms 34020 KB Output is correct
13 Correct 357 ms 35560 KB Output is correct
14 Correct 489 ms 37484 KB Output is correct
15 Correct 150 ms 36352 KB Output is correct
16 Correct 156 ms 36204 KB Output is correct
17 Correct 142 ms 35308 KB Output is correct
18 Correct 110 ms 35304 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 144856 KB Output is correct
2 Correct 560 ms 144960 KB Output is correct
3 Correct 1805 ms 150892 KB Output is correct
4 Correct 537 ms 144876 KB Output is correct
5 Correct 611 ms 139116 KB Output is correct
6 Correct 429 ms 139116 KB Output is correct
7 Correct 608 ms 138988 KB Output is correct
8 Correct 452 ms 139020 KB Output is correct
9 Correct 175 ms 132060 KB Output is correct
10 Correct 183 ms 138228 KB Output is correct
11 Correct 250 ms 138076 KB Output is correct
12 Correct 525 ms 138332 KB Output is correct
13 Correct 1614 ms 139872 KB Output is correct
14 Correct 2072 ms 153884 KB Output is correct
15 Correct 661 ms 150884 KB Output is correct
16 Correct 681 ms 150764 KB Output is correct
17 Correct 412 ms 145292 KB Output is correct
18 Correct 416 ms 145232 KB Output is correct