oj.uz

Submission #589764

# Submission time Handle Problem Language Result Execution time Memory
589764 2022-07-05T08:52:58 Z Lucpp Comparing Plants (IOI20_plants) C++17
100 / 100
 1809 ms 97056 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
const int LOG = 18;
int n, k, cap;
vector<vector<int>> jumpL, jumpR;
vector<int> h;

struct Data{
	int m = INF, l, r, ind = -1;
};
Data combine(Data a, Data b){
	Data d;
	d.m = min(a.m, b.m);
	if(d.m == a.m) d.l = a.l;
	else d.l = b.l;
	if(d.m == b.m) d.r = b.r;
	else d.r = a.r;
	if(d.m == a.m && a.ind != -1) d.ind = a.ind;
	if(d.m == b.m && b.ind != -1) d.ind = b.ind;
	if(d.m == a.m && d.m == b.m && b.l-a.r >= k) d.ind = b.l;
	return d;
}
vector<Data> S;
vector<int> O;
vector<bool> lazy;
void build(vector<int> v){
	for(cap = 1; cap < (int)v.size(); cap *= 2);
	S.resize(2*cap);
	O.resize(2*cap);
	lazy.resize(2*cap);
	for(int i = 0; i < (int)v.size(); i++) S[i+cap] = Data{v[i], i+1, i+1};
	for(int i = cap-1; i > 0; i--) S[i] = combine(S[2*i], S[2*i+1]);
}
void apply(int v, int i){
	lazy[i] = true;
	O[i] += v;
	S[i].m += v;
}
void push(int i){
	if(lazy[i]){
		apply(O[i], 2*i);
		apply(O[i], 2*i+1);
		O[i] = 0;
		lazy[i] = false;
	}
}
void upd(int p, int v, int a, int b, int i){
	if(a == b) S[i] = {v, p, p, -1};
	else{
		push(i);
		int m = (a+b)/2;
		if(p <= m) upd(p, v, a, m, 2*i);
		else upd(p, v, m+1, b, 2*i+1);
		S[i] = combine(S[2*i], S[2*i+1]);
	}
}
void apply(int l, int r, int v, int a, int b, int i){
	if(l <= a && b <= r) apply(v, i);
	else if(b < l || r < a) return;
	else{
		push(i);
		int m = (a+b)/2;
		apply(l, r, v, a, m, 2*i);
		apply(l, r, v, m+1, b, 2*i+1);
		S[i] = combine(S[2*i], S[2*i+1]);
	}
}

vector<pair<int, int>> S2;
void build2(){
	S2.resize(2*cap, {INF, 0});
	for(int i = cap; i < 2*cap; i++) S2[i].second = i-cap;
}
void upd2(int i, int v){
	i += cap;
	S2[i].first = v;
	while(i > 1){
		i /= 2;
		S2[i] = min(S2[2*i], S2[2*i+1]);
	}
}
pair<int, int> qry2(int l, int r, int a, int b, int i){
	if(l <= a && b <= r) return S2[i];
	if(b < l || r < a) return {INF, 0};
	int m = (a+b)/2;
	return min(qry2(l, r, a, m, 2*i), qry2(l, r, m+1, b, 2*i+1));
}


bool findR(int a, int b){
	for(int i = LOG-1; i >= 0; i--){
		if(jumpR[i][a] == -1) continue;
		if(jumpR[i][a] <= b) a = jumpR[i][a];
	}
	return b-a<k && h[a] <= h[b];
}
bool findL(int a, int b){
	for(int i = LOG-1; i >= 0; i--){
		if(jumpL[i][a] == -1) continue;
		if(jumpL[i][a] >= b) a = jumpL[i][a];
	}
	return a-b<k && h[a] <= h[b];
}

void init(int K, vector<int> r) {
	k = K;
	n = (int)r.size();
	h.resize(2*n);
	r.resize(2*n);
	jumpL.assign(LOG, vector<int>(2*n, -1));
	jumpR.assign(LOG, vector<int>(2*n, -1));
	for(int i = 0; i < n; i++) r[i+n] = r[i];
	build(r);
	build2();
	for(int it = 0; it < n; it++){
		assert(S[1].m == 0);
		assert(S[1].ind != -1);
		int i = S[1].ind;
		i = (i-1)%n;
		h[i] = h[i+n] = n-it;
		upd2(i, h[i]);
		upd2(i+n, h[i]);

		auto p = qry2(i+2, i+k, 1, cap, 1);
		if(p.first != INF) jumpR[0][i] = p.second;
		p = qry2(i+n+2, i+n+k, 1, cap, 1);
		if(p.first != INF) jumpR[0][i+n] = p.second;
		p = qry2(i-k+2, i, 1, cap, 1);
		if(p.first != INF) jumpL[0][i] = p.second;
		p = qry2(i+n-k+2, i+n, 1, cap, 1);
		if(p.first != INF) jumpL[0][i+n] = p.second;

		upd(i+1, INF, 1, cap, 1);
		upd(i+n+1, INF, 1, cap, 1);
		apply(max(0, i-k+1)+1, i, -1, 1, cap, 1);
		apply(i+n-k+2, i+n, -1, 1, cap, 1);
		apply(i+2*n-k+2, 2*n, -1, 1, cap, 1);

	}
	for(int i = 1; i < LOG; i++){
		for(int j = 0; j < 2*n; j++){
			if(jumpR[i-1][j] != -1) jumpR[i][j] = jumpR[i-1][jumpR[i-1][j]];
			if(jumpL[i-1][j] != -1) jumpL[i][j] = jumpL[i-1][jumpL[i-1][j]];
		}
	}
	
}

int compare_plants(int x, int y) {
	if(h[x] < h[y]){
		if(findR(x, y) || findL(x+n, y)) return -1;
		else return 0;
	}
	else{
		if(findR(y, x+n) || findL(y, x)) return 1;
		else return 0;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 58 ms 3092 KB Output is correct
7 Correct 158 ms 12748 KB Output is correct
8 Correct 809 ms 93496 KB Output is correct
9 Correct 769 ms 93392 KB Output is correct
10 Correct 763 ms 93388 KB Output is correct
11 Correct 807 ms 93392 KB Output is correct
12 Correct 813 ms 93388 KB Output is correct
13 Correct 834 ms 93392 KB Output is correct
14 Correct 631 ms 93388 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 784 KB Output is correct
7 Correct 84 ms 5512 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 86 ms 5584 KB Output is correct
11 Correct 102 ms 5424 KB Output is correct
12 Correct 91 ms 5616 KB Output is correct
13 Correct 104 ms 5560 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 784 KB Output is correct
7 Correct 84 ms 5512 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 5 ms 724 KB Output is correct
10 Correct 86 ms 5584 KB Output is correct
11 Correct 102 ms 5424 KB Output is correct
12 Correct 91 ms 5616 KB Output is correct
13 Correct 104 ms 5560 KB Output is correct
14 Correct 194 ms 12812 KB Output is correct
15 Correct 1705 ms 93392 KB Output is correct
16 Correct 185 ms 12752 KB Output is correct
17 Correct 1753 ms 93492 KB Output is correct
18 Correct 1166 ms 93392 KB Output is correct
19 Correct 874 ms 93504 KB Output is correct
20 Correct 1488 ms 93392 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 85 ms 3876 KB Output is correct
4 Correct 858 ms 93392 KB Output is correct
5 Correct 1097 ms 93388 KB Output is correct
6 Correct 1391 ms 93388 KB Output is correct
7 Correct 1592 ms 93396 KB Output is correct
8 Correct 1653 ms 93388 KB Output is correct
9 Correct 998 ms 93392 KB Output is correct
10 Correct 845 ms 93392 KB Output is correct
11 Correct 808 ms 93396 KB Output is correct
12 Correct 722 ms 93396 KB Output is correct
13 Correct 1053 ms 93380 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 17 ms 1364 KB Output is correct
8 Correct 14 ms 1400 KB Output is correct
9 Correct 15 ms 1340 KB Output is correct
10 Correct 14 ms 1364 KB Output is correct
11 Correct 14 ms 1364 KB Output is correct
12 Correct 16 ms 1340 KB Output is correct
13 Correct 13 ms 1364 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 4 ms 696 KB Output is correct
6 Correct 882 ms 95616 KB Output is correct
7 Correct 1271 ms 95892 KB Output is correct
8 Correct 1706 ms 96004 KB Output is correct
9 Correct 1731 ms 96200 KB Output is correct
10 Correct 982 ms 95548 KB Output is correct
11 Correct 1183 ms 96156 KB Output is correct
12 Correct 747 ms 95440 KB Output is correct
13 Correct 944 ms 95720 KB Output is correct
14 Correct 1421 ms 95912 KB Output is correct
15 Correct 1484 ms 96012 KB Output is correct
16 Correct 753 ms 95488 KB Output is correct
17 Correct 858 ms 95532 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 58 ms 3092 KB Output is correct
7 Correct 158 ms 12748 KB Output is correct
8 Correct 809 ms 93496 KB Output is correct
9 Correct 769 ms 93392 KB Output is correct
10 Correct 763 ms 93388 KB Output is correct
11 Correct 807 ms 93392 KB Output is correct
12 Correct 813 ms 93388 KB Output is correct
13 Correct 834 ms 93392 KB Output is correct
14 Correct 631 ms 93388 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 5 ms 784 KB Output is correct
21 Correct 84 ms 5512 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 5 ms 724 KB Output is correct
24 Correct 86 ms 5584 KB Output is correct
25 Correct 102 ms 5424 KB Output is correct
26 Correct 91 ms 5616 KB Output is correct
27 Correct 104 ms 5560 KB Output is correct
28 Correct 194 ms 12812 KB Output is correct
29 Correct 1705 ms 93392 KB Output is correct
30 Correct 185 ms 12752 KB Output is correct
31 Correct 1753 ms 93492 KB Output is correct
32 Correct 1166 ms 93392 KB Output is correct
33 Correct 874 ms 93504 KB Output is correct
34 Correct 1488 ms 93392 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 85 ms 3876 KB Output is correct
38 Correct 858 ms 93392 KB Output is correct
39 Correct 1097 ms 93388 KB Output is correct
40 Correct 1391 ms 93388 KB Output is correct
41 Correct 1592 ms 93396 KB Output is correct
42 Correct 1653 ms 93388 KB Output is correct
43 Correct 998 ms 93392 KB Output is correct
44 Correct 845 ms 93392 KB Output is correct
45 Correct 808 ms 93396 KB Output is correct
46 Correct 722 ms 93396 KB Output is correct
47 Correct 1053 ms 93380 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 2 ms 340 KB Output is correct
54 Correct 17 ms 1364 KB Output is correct
55 Correct 14 ms 1400 KB Output is correct
56 Correct 15 ms 1340 KB Output is correct
57 Correct 14 ms 1364 KB Output is correct
58 Correct 14 ms 1364 KB Output is correct
59 Correct 16 ms 1340 KB Output is correct
60 Correct 13 ms 1364 KB Output is correct
61 Correct 107 ms 5596 KB Output is correct
62 Correct 152 ms 14920 KB Output is correct
63 Correct 1006 ms 96304 KB Output is correct
64 Correct 1123 ms 96488 KB Output is correct
65 Correct 1533 ms 96556 KB Output is correct
66 Correct 1661 ms 96940 KB Output is correct
67 Correct 1809 ms 97056 KB Output is correct
68 Correct 1065 ms 96524 KB Output is correct
69 Correct 1175 ms 97040 KB Output is correct
70 Correct 920 ms 96308 KB Output is correct
71 Correct 1127 ms 96484 KB Output is correct
72 Correct 1509 ms 96680 KB Output is correct
73 Correct 1730 ms 96872 KB Output is correct
74 Correct 983 ms 96376 KB Output is correct
75 Correct 1008 ms 96536 KB Output is correct