oj.uz

Submission #829492

# Submission time Handle Problem Language Result Execution time Memory
829492 2023-08-18T11:27:22 Z amunduzbaev Comparing Plants (IOI20_plants) C++17
5 / 100
 1474 ms 104200 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;

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<int>> l_, r_;
int n;

void init(int k, vector<int> r) {
	
	n = r.size();
	a.resize(n);
	
	l_.resize(n, vector<int>(20, -1));
	r_.resize(n, vector<int>(20, -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++) cout<<a[i]<<" ";
	//~ cout<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ cout<<l_[i][0]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ cout<<r_[i][0]<<" ";
	//~ } cout<<"\n";
	
	for(int j=1;j<20;j++){
		for(int i=0;i<n;i++){
			if(~l_[i][j - 1]) l_[i][j] = l_[l_[i][j - 1]][j - 1];
			if(~r_[i][j - 1]) r_[i][j] = r_[r_[i][j - 1]][j - 1];
		}
	}
	
	return;
}

bool check(int x, int y){
	{
		int cur = x;
		for(int j=19;~j;j--){
			if(l_[cur][j] == -1) continue;
			if(y < x){
				if(l_[cur][j] <= x && y <= l_[cur][j]) cur = l_[cur][j];
			} else {
				if(l_[cur][j] <= x || y <= l_[cur][j]) cur = l_[cur][j];
			}
		}
		
		if(cur == y) return true;
		//~ if(l_[cur][0] == -1) return false;
		if(~ l_[cur][0] && a[cur] > a[y]) return true;
	}
	
	{
		int cur = x;
		for(int j=19;~j;j--){
			if(r_[cur][j] == -1) continue;
			if(x < y){
				if(x <= r_[cur][j] && r_[cur][j] <= y) cur = r_[cur][j];
			} else {
				if(x <= r_[cur][j] || r_[cur][j] <= y) cur = r_[cur][j];
			}
		}
		
		if(cur == y) return true;
		//~ if(r_[cur][0] == -1) return false;
		if(~r_[cur][0] && a[cur] > 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 14 ms 33364 KB Output is correct
2 Correct 12 ms 33252 KB Output is correct
3 Correct 12 ms 33280 KB Output is correct
4 Correct 15 ms 33324 KB Output is correct
5 Correct 13 ms 33296 KB Output is correct
6 Correct 69 ms 37140 KB Output is correct
7 Correct 225 ms 44792 KB Output is correct
8 Correct 1177 ms 104192 KB Output is correct
9 Correct 1223 ms 104188 KB Output is correct
10 Correct 1136 ms 104196 KB Output is correct
11 Correct 1212 ms 104200 KB Output is correct
12 Correct 1237 ms 104196 KB Output is correct
13 Correct 1286 ms 104196 KB Output is correct
14 Correct 1474 ms 104196 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33364 KB Output is correct
2 Correct 16 ms 33340 KB Output is correct
3 Correct 12 ms 33364 KB Output is correct
4 Correct 12 ms 33364 KB Output is correct
5 Incorrect 14 ms 33396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33364 KB Output is correct
2 Correct 16 ms 33340 KB Output is correct
3 Correct 12 ms 33364 KB Output is correct
4 Correct 12 ms 33364 KB Output is correct
5 Incorrect 14 ms 33396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33260 KB Output is correct
2 Correct 12 ms 33352 KB Output is correct
3 Incorrect 98 ms 38480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 33364 KB Output is correct
2 Correct 14 ms 33260 KB Output is correct
3 Correct 16 ms 33292 KB Output is correct
4 Correct 13 ms 33292 KB Output is correct
5 Correct 15 ms 33344 KB Output is correct
6 Correct 17 ms 33432 KB Output is correct
7 Correct 29 ms 34300 KB Output is correct
8 Incorrect 35 ms 34364 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33364 KB Output is correct
2 Correct 15 ms 33364 KB Output is correct
3 Correct 14 ms 33248 KB Output is correct
4 Correct 12 ms 33264 KB Output is correct
5 Incorrect 18 ms 33620 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33364 KB Output is correct
2 Correct 12 ms 33252 KB Output is correct
3 Correct 12 ms 33280 KB Output is correct
4 Correct 15 ms 33324 KB Output is correct
5 Correct 13 ms 33296 KB Output is correct
6 Correct 69 ms 37140 KB Output is correct
7 Correct 225 ms 44792 KB Output is correct
8 Correct 1177 ms 104192 KB Output is correct
9 Correct 1223 ms 104188 KB Output is correct
10 Correct 1136 ms 104196 KB Output is correct
11 Correct 1212 ms 104200 KB Output is correct
12 Correct 1237 ms 104196 KB Output is correct
13 Correct 1286 ms 104196 KB Output is correct
14 Correct 1474 ms 104196 KB Output is correct
15 Correct 13 ms 33364 KB Output is correct
16 Correct 16 ms 33340 KB Output is correct
17 Correct 12 ms 33364 KB Output is correct
18 Correct 12 ms 33364 KB Output is correct
19 Incorrect 14 ms 33396 KB Output isn't correct
20 Halted 0 ms 0 KB -