oj.uz

Submission #827718

# Submission time Handle Problem Language Result Execution time Memory
827718 2023-08-16T16:50:16 Z amunduzbaev Comparing Plants (IOI20_plants) C++17
55 / 100
 1100 ms 33424 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] = 1;
			
			for(int i=0;i<n;i++){
				if((i <= p && p < i + k) || (i <= p + n && p + n < i + k)){
					if(!a[i]) is[p][i] = 1;
					r[i]--;
				}
				if((p <= i && i < p + k) || (p <= i + n && i + n < p + k)){
					if(!a[i]) is[p][i] = 1;
				}
			}
		}
		
		//~ for(int i=0;i<n;i++){
			//~ for(int j=0;j<n;j++){
				//~ cout<<is[i][j]<<" ";
			//~ } cout<<"\n";
		//~ } cout<<"\n";
		
		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 7 ms 16724 KB Output is correct
2 Correct 7 ms 16712 KB Output is correct
3 Correct 9 ms 16696 KB Output is correct
4 Correct 8 ms 16728 KB Output is correct
5 Correct 8 ms 16684 KB Output is correct
6 Correct 44 ms 20444 KB Output is correct
7 Incorrect 88 ms 22736 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 7 ms 16724 KB Output is correct
3 Correct 7 ms 16708 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16744 KB Output is correct
6 Correct 12 ms 16980 KB Output is correct
7 Correct 68 ms 21816 KB Output is correct
8 Correct 9 ms 16852 KB Output is correct
9 Correct 13 ms 16968 KB Output is correct
10 Correct 73 ms 21760 KB Output is correct
11 Correct 58 ms 21664 KB Output is correct
12 Correct 60 ms 21828 KB Output is correct
13 Correct 67 ms 21700 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 7 ms 16724 KB Output is correct
3 Correct 7 ms 16708 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16744 KB Output is correct
6 Correct 12 ms 16980 KB Output is correct
7 Correct 68 ms 21816 KB Output is correct
8 Correct 9 ms 16852 KB Output is correct
9 Correct 13 ms 16968 KB Output is correct
10 Correct 73 ms 21760 KB Output is correct
11 Correct 58 ms 21664 KB Output is correct
12 Correct 60 ms 21828 KB Output is correct
13 Correct 67 ms 21700 KB Output is correct
14 Correct 126 ms 22896 KB Output is correct
15 Correct 1100 ms 33368 KB Output is correct
16 Correct 127 ms 22860 KB Output is correct
17 Correct 1053 ms 33368 KB Output is correct
18 Correct 663 ms 32948 KB Output is correct
19 Correct 760 ms 33420 KB Output is correct
20 Correct 1012 ms 33424 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16720 KB Output is correct
3 Correct 52 ms 21452 KB Output is correct
4 Correct 534 ms 32568 KB Output is correct
5 Correct 659 ms 32736 KB Output is correct
6 Correct 830 ms 32928 KB Output is correct
7 Correct 1010 ms 33132 KB Output is correct
8 Correct 1087 ms 33320 KB Output is correct
9 Correct 593 ms 32664 KB Output is correct
10 Correct 625 ms 32680 KB Output is correct
11 Correct 415 ms 32516 KB Output is correct
12 Correct 585 ms 32752 KB Output is correct
13 Correct 625 ms 32784 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16620 KB Output is correct
3 Correct 7 ms 16724 KB Output is correct
4 Correct 7 ms 16724 KB Output is correct
5 Correct 7 ms 16664 KB Output is correct
6 Correct 9 ms 16852 KB Output is correct
7 Correct 57 ms 17936 KB Output is correct
8 Correct 58 ms 17932 KB Output is correct
9 Correct 61 ms 17968 KB Output is correct
10 Correct 59 ms 17928 KB Output is correct
11 Correct 57 ms 17932 KB Output is correct
12 Correct 61 ms 17928 KB Output is correct
13 Correct 57 ms 17940 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 8 ms 16724 KB Output is correct
4 Correct 8 ms 16612 KB Output is correct
5 Incorrect 11 ms 16864 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16712 KB Output is correct
3 Correct 9 ms 16696 KB Output is correct
4 Correct 8 ms 16728 KB Output is correct
5 Correct 8 ms 16684 KB Output is correct
6 Correct 44 ms 20444 KB Output is correct
7 Incorrect 88 ms 22736 KB Output isn't correct
8 Halted 0 ms 0 KB -