oj.uz

Submission #827713

# Submission time Handle Problem Language Result Execution time Memory
827713 2023-08-16T16:48:16 Z amunduzbaev Comparing Plants (IOI20_plants) C++17
0 / 100
 10 ms 16732 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;

vector<int> a;
vector<vector<int>> is;
int n;

void init(int k, vector<int> r) {
	
	n = r.size();
	a.resize(n);
	
	if(n <= 300){
		is.resize(n, vector<int>(n, 0));
		
		for(int j=n;j>0;j--){
			int cnt = 0;
			for(int i=0;i<k - 1;i++) cnt += (r[i] == 0);
			int p = -1;
			for(int i=k - 1;;){
				if(!cnt && r[i] == 0){
					p = i;
					break;
				}
				
				cnt -= (r[(i + n - k + 1) % n] == 0);
				cnt += (r[i] == 0);
				i = (i + 1) % n;
				if(i == k - 1) break;
			}
			
			assert(a[p] == 0);
			r[p] = inf;
			a[p] = j;
			
			for(int i=0;i<n;i++){
				if((i <= p && p < i + k) || (i <= p + n && p + n < i + k)){
					is[p][i] = 1;
					r[i]--;
				}
				if((p <= i && i < p + k) || (p <= i + n && i + n < p + k)){
					is[p][i] = 1;
				}
			}
		}
		
		for(int k=0;k<n;k++){
			for(int j=0;j<n;j++){
				for(int i=0;i<n;i++){
					is[i][j] |= (is[i][k] & is[k][j]);
				}
			}
		}
		
		return;
	}
	
	{
		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);
			
			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;
		}
	}
	
	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);
		
		assert(v == 0);
		
		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);
		}
	}
	
	return;
}

int compare_plants(int x, int y) {
	if(n <= 300){
		if(is[x][y]) return 1;
		if(is[y][x]) return -1;
		return 0;
	}
	if(a[x] > a[y]) return 1;
	if(a[x] < a[y]) return -1;
	
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16720 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Incorrect 8 ms 16684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16728 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Incorrect 8 ms 16724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16728 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Incorrect 8 ms 16724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16652 KB Output is correct
3 Incorrect 9 ms 16724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16724 KB Output is correct
3 Incorrect 7 ms 16724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16720 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Incorrect 8 ms 16684 KB Output isn't correct
4 Halted 0 ms 0 KB -