oj.uz

Submission #829526

# Submission time Handle Problem Language Result Execution time Memory
829526 2023-08-18T12:02:05 Z amunduzbaev Comparing Plants (IOI20_plants) C++17
100 / 100
 3247 ms 136364 KB 
#include "plants.h"

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
//~ #define int ll

const int inf = 1e9;
const int N = 2e5 + 5;
const int M = 20;

struct ST{
	ar<ll, 2> tree[N << 2];
	ll f[N << 2];
	
	void build(int lx, int rx, int x){
		if(lx == rx) { tree[x][1] = lx; return; };
		int m = (lx + rx) >> 1;
		build(lx, m, x << 1), build(m + 1, rx, x << 1 | 1);
		tree[x][1] = lx;
	}
	
	ST(){
		build(0, N, 1);
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		tree[x << 1][0] += f[x];
		tree[x << 1 | 1][0] += f[x];
		f[x << 1] += f[x], f[x << 1 | 1] += f[x];
		f[x] = 0;
	}
	
	void add(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x][0] += v;
			f[x] += v;
			return;
		}
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, x << 1), add(l, r, v, m + 1, rx, x << 1 | 1);
		tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
	}
	
	void add(int l, int r, int v) { return add(l, r, v, 0, N, 1); }
	
	ar<ll, 2> get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return {inf, inf};
		if(lx >= l && rx <= r) return tree[x];
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		return min(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
	
	ar<ll, 2> get(int l, int r){
		return get(l, r, 0, N, 1);
	}
}tree, R, builder, buildel;

vector<int> a;
vector<vector<ll>> l_, r_;
int n;

void init(int k, vector<int> r) {
	
	n = r.size();
	a.resize(n);
	
	l_.resize(n, vector<ll>(M, -1));
	r_.resize(n, vector<ll>(M, -1));
	
	{
		int cnt = 0;
		for(int i=0;i<k - 1;i++) cnt += (r[i] == 0);
		for(int i=k - 1;;){
			tree.add(i, i, r[i] + cnt);
			buildel.add(i, i, 1);
			builder.add(i, i, 1);
			
			if(r[i]){
				R.add(i, i, r[i]);
			} else {
				R.add(i, i, inf);
			}
			
			cnt -= (r[(i + n - k + 1) % n] == 0);
			cnt += (r[i] == 0);
			i = (i + 1) % n;
			if(i == k - 1) break;
		}
	}
	
	auto to_r = [&](int p){
		int l = p, r = p + k - 1;
		ar<ll, 2> pp = buildel.get(l, min(r, n - 1));
		if(!pp[0] || r < n) return pp;
		return buildel.get(0, r - n);
	};
	auto to_l = [&](int p){
		int l = p - k + 1, r = p;
		ar<ll, 2> pp = builder.get(max(l, 0), r);
		if(!pp[0] || 0 <= l) return pp;
		return builder.get(n + l, n - 1);
	};
	
	for(int j=n;j>0;j--){
		//~ for(int i=0;i<n;i++) cout<<tree.get(i, i)[0]<<" ";
		//~ cout<<"\n";
		
		auto [v, p] = tree.get(0, n - 1);
		
		{
			ar<ll, 2> pp = to_r(p);
			while(pp[0] == 0){
				l_[pp[1]][0] = p;
				buildel.add(pp[1], pp[1], 1);
				pp = to_r(p);
			}
			pp = to_l(p);
			while(pp[0] == 0){
				r_[pp[1]][0] = p;
				builder.add(pp[1], pp[1], 1);
				pp = to_l(p);
			}
		}
		
		assert(v == 0);
		buildel.add(p, p, -1);
		builder.add(p, p, -1);
		
		a[p] = j;
		
		R.add(p, p, inf);
		tree.add(p, p, inf);
		{
			int l = p - k + 1, r = p;
			tree.add(max(l, 0), r, -1);
			R.add(max(l, 0), r, -1);
			if(l < 0) tree.add(n + l, n - 1, -1);
			if(l < 0) R.add(n + l, n - 1, -1);
			
			ar<ll, 2> pp = R.get(0, n - 1);
			while(pp[0] == 0){
				R.add(pp[1], pp[1], inf);
				{
					int l = pp[1] + 1, r = pp[1] + k - 1;
					tree.add(l, min(r, n - 1), 1);
					if(n <= r) tree.add(0,  r - n, 1);
				}
				pp = R.get(0, n - 1);
			}
		}
		{
			int l = p, r = p + k - 1;
			tree.add(l, min(r, n - 1), -1);
			if(n <= r) tree.add(0,  r - n, -1);
		}
	}
	
	for(int i=0;i<n;i++){
		if(~l_[i][0]) l_[i][0] = (i - l_[i][0] + n) % n;
		else l_[i][0] = 0;
		
		if(~r_[i][0]) r_[i][0] = (r_[i][0] - i + n) % n;
		else r_[i][0] = 0;
	}
	
	for(int j=1;j<M;j++){
		for(int i=0;i<n;i++){
			l_[i][j] = l_[i][j - 1] + l_[(i - l_[i][j - 1] % n + n) % n][j - 1];
			r_[i][j] = r_[i][j - 1] + r_[(i + r_[i][j - 1]) % n][j - 1];
		}
	}
	
	return;
}

bool check(int x, int y){
	{
		int cur = x, dis = (x - y + n) % n;
		for(int j=19;~j;j--){
			if(dis > l_[cur][j]){
				dis -= l_[cur][j];
				cur = (cur - l_[cur][j] % n + n) % n;
			}
		}
		
		if(l_[cur][0] && a[(y + dis) % n] > a[y]) return true;
	}
	
	{
		int cur = x, dis = (y - x + n) % n;
		for(int j=19;~j;j--){
			if(dis > r_[cur][j]){
				dis -= r_[cur][j];
				cur = (cur + r_[cur][j]) % n;
			}
		}
		
		if(r_[cur][0] && a[(y - dis + n) % n] > a[y]) return true;
	}
	
	return false;
}

int compare_plants(int x, int y) {
	if(check(x, y)) return 1;
	if(check(y, x)) return -1;
	
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33296 KB Output is correct
2 Correct 12 ms 33280 KB Output is correct
3 Correct 11 ms 33364 KB Output is correct
4 Correct 13 ms 33284 KB Output is correct
5 Correct 12 ms 33360 KB Output is correct
6 Correct 157 ms 36108 KB Output is correct
7 Correct 250 ms 45780 KB Output is correct
8 Correct 1342 ms 132592 KB Output is correct
9 Correct 1262 ms 132588 KB Output is correct
10 Correct 1260 ms 132588 KB Output is correct
11 Correct 1532 ms 132556 KB Output is correct
12 Correct 1485 ms 132588 KB Output is correct
13 Correct 1330 ms 132588 KB Output is correct
14 Correct 1350 ms 132632 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33248 KB Output is correct
2 Correct 14 ms 33284 KB Output is correct
3 Correct 14 ms 33364 KB Output is correct
4 Correct 12 ms 33364 KB Output is correct
5 Correct 12 ms 33364 KB Output is correct
6 Correct 25 ms 33868 KB Output is correct
7 Correct 110 ms 38608 KB Output is correct
8 Correct 14 ms 33364 KB Output is correct
9 Correct 20 ms 33780 KB Output is correct
10 Correct 120 ms 38508 KB Output is correct
11 Correct 135 ms 38488 KB Output is correct
12 Correct 180 ms 38600 KB Output is correct
13 Correct 115 ms 38500 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33248 KB Output is correct
2 Correct 14 ms 33284 KB Output is correct
3 Correct 14 ms 33364 KB Output is correct
4 Correct 12 ms 33364 KB Output is correct
5 Correct 12 ms 33364 KB Output is correct
6 Correct 25 ms 33868 KB Output is correct
7 Correct 110 ms 38608 KB Output is correct
8 Correct 14 ms 33364 KB Output is correct
9 Correct 20 ms 33780 KB Output is correct
10 Correct 120 ms 38508 KB Output is correct
11 Correct 135 ms 38488 KB Output is correct
12 Correct 180 ms 38600 KB Output is correct
13 Correct 115 ms 38500 KB Output is correct
14 Correct 394 ms 45840 KB Output is correct
15 Correct 2576 ms 132588 KB Output is correct
16 Correct 247 ms 48008 KB Output is correct
17 Correct 3247 ms 136356 KB Output is correct
18 Correct 1768 ms 135880 KB Output is correct
19 Correct 2041 ms 136364 KB Output is correct
20 Correct 2362 ms 136364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 33364 KB Output is correct
2 Correct 12 ms 33364 KB Output is correct
3 Correct 149 ms 37056 KB Output is correct
4 Correct 1580 ms 132584 KB Output is correct
5 Correct 1790 ms 132644 KB Output is correct
6 Correct 2188 ms 132544 KB Output is correct
7 Correct 2418 ms 132592 KB Output is correct
8 Correct 2859 ms 132520 KB Output is correct
9 Correct 1604 ms 135704 KB Output is correct
10 Correct 1751 ms 135612 KB Output is correct
11 Correct 1230 ms 135512 KB Output is correct
12 Correct 1443 ms 135708 KB Output is correct
13 Correct 1597 ms 135728 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33284 KB Output is correct
2 Correct 15 ms 33280 KB Output is correct
3 Correct 16 ms 33336 KB Output is correct
4 Correct 15 ms 33340 KB Output is correct
5 Correct 19 ms 33336 KB Output is correct
6 Correct 19 ms 33404 KB Output is correct
7 Correct 53 ms 34020 KB Output is correct
8 Correct 29 ms 34068 KB Output is correct
9 Correct 41 ms 34076 KB Output is correct
10 Correct 30 ms 34100 KB Output is correct
11 Correct 50 ms 34092 KB Output is correct
12 Correct 47 ms 34072 KB Output is correct
13 Correct 32 ms 34084 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33364 KB Output is correct
2 Correct 15 ms 33364 KB Output is correct
3 Correct 14 ms 33364 KB Output is correct
4 Correct 14 ms 33280 KB Output is correct
5 Correct 21 ms 33852 KB Output is correct
6 Correct 1608 ms 132588 KB Output is correct
7 Correct 2080 ms 132592 KB Output is correct
8 Correct 2215 ms 132556 KB Output is correct
9 Correct 2574 ms 132584 KB Output is correct
10 Correct 1569 ms 134752 KB Output is correct
11 Correct 1924 ms 135360 KB Output is correct
12 Correct 1479 ms 134636 KB Output is correct
13 Correct 1774 ms 134812 KB Output is correct
14 Correct 2054 ms 135008 KB Output is correct
15 Correct 2363 ms 135200 KB Output is correct
16 Correct 1480 ms 134676 KB Output is correct
17 Correct 1661 ms 134852 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33296 KB Output is correct
2 Correct 12 ms 33280 KB Output is correct
3 Correct 11 ms 33364 KB Output is correct
4 Correct 13 ms 33284 KB Output is correct
5 Correct 12 ms 33360 KB Output is correct
6 Correct 157 ms 36108 KB Output is correct
7 Correct 250 ms 45780 KB Output is correct
8 Correct 1342 ms 132592 KB Output is correct
9 Correct 1262 ms 132588 KB Output is correct
10 Correct 1260 ms 132588 KB Output is correct
11 Correct 1532 ms 132556 KB Output is correct
12 Correct 1485 ms 132588 KB Output is correct
13 Correct 1330 ms 132588 KB Output is correct
14 Correct 1350 ms 132632 KB Output is correct
15 Correct 13 ms 33248 KB Output is correct
16 Correct 14 ms 33284 KB Output is correct
17 Correct 14 ms 33364 KB Output is correct
18 Correct 12 ms 33364 KB Output is correct
19 Correct 12 ms 33364 KB Output is correct
20 Correct 25 ms 33868 KB Output is correct
21 Correct 110 ms 38608 KB Output is correct
22 Correct 14 ms 33364 KB Output is correct
23 Correct 20 ms 33780 KB Output is correct
24 Correct 120 ms 38508 KB Output is correct
25 Correct 135 ms 38488 KB Output is correct
26 Correct 180 ms 38600 KB Output is correct
27 Correct 115 ms 38500 KB Output is correct
28 Correct 394 ms 45840 KB Output is correct
29 Correct 2576 ms 132588 KB Output is correct
30 Correct 247 ms 48008 KB Output is correct
31 Correct 3247 ms 136356 KB Output is correct
32 Correct 1768 ms 135880 KB Output is correct
33 Correct 2041 ms 136364 KB Output is correct
34 Correct 2362 ms 136364 KB Output is correct
35 Correct 11 ms 33364 KB Output is correct
36 Correct 12 ms 33364 KB Output is correct
37 Correct 149 ms 37056 KB Output is correct
38 Correct 1580 ms 132584 KB Output is correct
39 Correct 1790 ms 132644 KB Output is correct
40 Correct 2188 ms 132544 KB Output is correct
41 Correct 2418 ms 132592 KB Output is correct
42 Correct 2859 ms 132520 KB Output is correct
43 Correct 1604 ms 135704 KB Output is correct
44 Correct 1751 ms 135612 KB Output is correct
45 Correct 1230 ms 135512 KB Output is correct
46 Correct 1443 ms 135708 KB Output is correct
47 Correct 1597 ms 135728 KB Output is correct
48 Correct 17 ms 33284 KB Output is correct
49 Correct 15 ms 33280 KB Output is correct
50 Correct 16 ms 33336 KB Output is correct
51 Correct 15 ms 33340 KB Output is correct
52 Correct 19 ms 33336 KB Output is correct
53 Correct 19 ms 33404 KB Output is correct
54 Correct 53 ms 34020 KB Output is correct
55 Correct 29 ms 34068 KB Output is correct
56 Correct 41 ms 34076 KB Output is correct
57 Correct 30 ms 34100 KB Output is correct
58 Correct 50 ms 34092 KB Output is correct
59 Correct 47 ms 34072 KB Output is correct
60 Correct 32 ms 34084 KB Output is correct
61 Correct 210 ms 38800 KB Output is correct
62 Correct 366 ms 47860 KB Output is correct
63 Correct 1610 ms 135504 KB Output is correct
64 Correct 1793 ms 135684 KB Output is correct
65 Correct 2179 ms 135872 KB Output is correct
66 Correct 2405 ms 136068 KB Output is correct
67 Correct 2564 ms 136268 KB Output is correct
68 Correct 1696 ms 135620 KB Output is correct
69 Correct 2069 ms 136228 KB Output is correct
70 Correct 1671 ms 135512 KB Output is correct
71 Correct 2053 ms 135680 KB Output is correct
72 Correct 2257 ms 135880 KB Output is correct
73 Correct 2448 ms 136120 KB Output is correct
74 Correct 1593 ms 135616 KB Output is correct
75 Correct 1606 ms 135732 KB Output is correct