oj.uz

Submission #829472

# Submission time Handle Problem Language Result Execution time Memory
829472 2023-08-18T11:09:52 Z amunduzbaev Comparing Plants (IOI20_plants) C++17
0 / 100
 18 ms 33372 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<<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(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(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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33364 KB Output is correct
2 Correct 14 ms 33372 KB Output is correct
3 Correct 14 ms 33256 KB Output is correct
4 Incorrect 17 ms 33328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33268 KB Output is correct
2 Correct 14 ms 33328 KB Output is correct
3 Incorrect 14 ms 33352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33268 KB Output is correct
2 Correct 14 ms 33328 KB Output is correct
3 Incorrect 14 ms 33352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 33288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33356 KB Output is correct
2 Correct 14 ms 33264 KB Output is correct
3 Incorrect 18 ms 33368 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33364 KB Output is correct
2 Correct 14 ms 33296 KB Output is correct
3 Incorrect 15 ms 33352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33364 KB Output is correct
2 Correct 14 ms 33372 KB Output is correct
3 Correct 14 ms 33256 KB Output is correct
4 Incorrect 17 ms 33328 KB Output isn't correct
5 Halted 0 ms 0 KB -