oj.uz

Submission #827558

# Submission time Handle Problem Language Result Execution time Memory
827558 2023-08-16T14:42:12 Z amunduzbaev Comparing Plants (IOI20_plants) C++17
44 / 100
 1111 ms 33428 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;
int n;

void init(int k, vector<int> r) {
	
	n = r.size();
	a.resize(n);
	
	{
		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(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 8 ms 16756 KB Output is correct
2 Correct 7 ms 16728 KB Output is correct
3 Correct 7 ms 16756 KB Output is correct
4 Incorrect 7 ms 16840 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16724 KB Output is correct
2 Correct 7 ms 16720 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 7 ms 16728 KB Output is correct
5 Correct 9 ms 16728 KB Output is correct
6 Correct 11 ms 16868 KB Output is correct
7 Correct 67 ms 21696 KB Output is correct
8 Correct 8 ms 16852 KB Output is correct
9 Correct 12 ms 16872 KB Output is correct
10 Correct 66 ms 21784 KB Output is correct
11 Correct 59 ms 21652 KB Output is correct
12 Correct 60 ms 21832 KB Output is correct
13 Correct 67 ms 21708 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16724 KB Output is correct
2 Correct 7 ms 16720 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 7 ms 16728 KB Output is correct
5 Correct 9 ms 16728 KB Output is correct
6 Correct 11 ms 16868 KB Output is correct
7 Correct 67 ms 21696 KB Output is correct
8 Correct 8 ms 16852 KB Output is correct
9 Correct 12 ms 16872 KB Output is correct
10 Correct 66 ms 21784 KB Output is correct
11 Correct 59 ms 21652 KB Output is correct
12 Correct 60 ms 21832 KB Output is correct
13 Correct 67 ms 21708 KB Output is correct
14 Correct 142 ms 22828 KB Output is correct
15 Correct 1111 ms 33368 KB Output is correct
16 Correct 129 ms 22864 KB Output is correct
17 Correct 1075 ms 33248 KB Output is correct
18 Correct 670 ms 32960 KB Output is correct
19 Correct 751 ms 33428 KB Output is correct
20 Correct 1028 ms 33428 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 11 ms 16732 KB Output is correct
3 Correct 52 ms 21452 KB Output is correct
4 Correct 544 ms 32572 KB Output is correct
5 Correct 670 ms 32740 KB Output is correct
6 Correct 850 ms 32932 KB Output is correct
7 Correct 957 ms 33132 KB Output is correct
8 Correct 1070 ms 33328 KB Output is correct
9 Correct 587 ms 32592 KB Output is correct
10 Correct 673 ms 32660 KB Output is correct
11 Correct 408 ms 32576 KB Output is correct
12 Correct 594 ms 32720 KB Output is correct
13 Correct 662 ms 32788 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16820 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 #6
0 / 15.0

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

Subtask #7
0 / 25.0

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