oj.uz

Submission #984128

# Submission time Handle Problem Language Result Execution time Memory
984128 2024-05-16T10:25:52 Z phoenix0423 Comparing Plants (IOI20_plants) C++17
32 / 100
 733 ms 41748 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int maxn = 4e5 + 5;
const int INF = 1e9;
#include "plants.h"

int a[maxn], rk[maxn];
int n, k;
vector<int> r;
pll st[maxn * 4];
ll tag[maxn * 4];

void cast(int v, int val){
	st[v].f += val, tag[v] += val;
}

void push(int v){
	if(tag[v]){
		cast(v * 2, tag[v]);
		cast(v * 2 + 1, tag[v]);
		tag[v] = 0;
	}
}

void upd(int l, int r, int val, int v = 1, int L = 0, int R = 2 * n - 1){
    if(l > R || r < L) return;
	if(L == R) st[v].s = L;
    if(l <= L && r >= R){
        st[v].f += val;
        tag[v] += val;
        return;
    }
    push(v);
	int m = (L + R) / 2;
	upd(l, r, val, v * 2, L, m);
	upd(l, r, val, v * 2 + 1, m + 1, R);
	st[v] = min(st[v * 2], st[v * 2 + 1]);
}

pll qry(int l, int r, int v = 1, int L = 0, int R = 2 * n - 1){
	if(l > R || r < L) return {INF, 0};
	if(l <= L && r >= R) return st[v];
	push(v);
	int m = (L + R) / 2;
	return min(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}

void init(int _k, std::vector<int> _r) {
	r = _r, k = _k;
	n = r.size();
	for(auto x : _r) r.pb(x);
	{
		for(int i = 0; i < 2 * n; i++) a[i] = 1 - r[i] * 2;
		for(int i = 1; i < 2 * n; i++) a[i] += a[i - 1];
	}
	for(int i = 0; i < 2 * n; i++) upd(i, i, r[i]);
	stack<int> stk;
	vector<int> used(2 * n + 1);
	for(int rd = 0; rd < n; rd++){
		if(stk.empty()) stk.push(qry(0, 2 * n - 1).s);
		while(true){
			int pos = stk.top();
			if(pos < n) pos += n;
			pll tmp = qry(pos - k + 1, pos - 1);
			if(!tmp.f){
				assert(!used[tmp.s]);
				pos = tmp.s, stk.push(pos);
				used[tmp.s] = 1;
			}
			else break;
		}
		int pos = stk.top(); stk.pop();
		pos %= n;
		rk[pos] = rd;
		upd(pos, pos, INF), upd(pos + n, pos + n, INF);
		upd(max(0, pos - k + 1), pos - 1, -1);
		pos += n;
		upd(pos - k + 1, pos - 1, -1);
	}
}

int compare_plants(int x, int y) {
	if(k <= 2){
		int m = a[y - 1] - (x ? a[x - 1] : 0);
		if(m == y - x) return 1;
		if(m == x - y) return -1;
		x += n;
		m = a[x - 1] - a[y - 1];
		if(m == x - y) return -1;
		if(m == y - x) return 1;
		return 0;
	}
	return rk[x] < rk[y] ? 1 : -1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4624 KB Output is correct
6 Correct 47 ms 7156 KB Output is correct
7 Correct 71 ms 10668 KB Output is correct
8 Correct 420 ms 35892 KB Output is correct
9 Correct 346 ms 35852 KB Output is correct
10 Correct 371 ms 35884 KB Output is correct
11 Correct 351 ms 36084 KB Output is correct
12 Correct 342 ms 35820 KB Output is correct
13 Correct 325 ms 35892 KB Output is correct
14 Correct 317 ms 35884 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 3 ms 4556 KB Output is correct
7 Correct 55 ms 11476 KB Output is correct
8 Correct 2 ms 4564 KB Output is correct
9 Correct 3 ms 4652 KB Output is correct
10 Correct 53 ms 11480 KB Output is correct
11 Correct 49 ms 11364 KB Output is correct
12 Correct 56 ms 11508 KB Output is correct
13 Correct 52 ms 11624 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 3 ms 4556 KB Output is correct
7 Correct 55 ms 11476 KB Output is correct
8 Correct 2 ms 4564 KB Output is correct
9 Correct 3 ms 4652 KB Output is correct
10 Correct 53 ms 11480 KB Output is correct
11 Correct 49 ms 11364 KB Output is correct
12 Correct 56 ms 11508 KB Output is correct
13 Correct 52 ms 11624 KB Output is correct
14 Correct 90 ms 12992 KB Output is correct
15 Correct 726 ms 41520 KB Output is correct
16 Correct 96 ms 12988 KB Output is correct
17 Correct 733 ms 41748 KB Output is correct
18 Correct 428 ms 41216 KB Output is correct
19 Correct 411 ms 41540 KB Output is correct
20 Correct 617 ms 41716 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 45 ms 9040 KB Output is correct
4 Correct 385 ms 40256 KB Output is correct
5 Correct 500 ms 40760 KB Output is correct
6 Incorrect 649 ms 41216 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4624 KB Output is correct
6 Correct 47 ms 7156 KB Output is correct
7 Correct 71 ms 10668 KB Output is correct
8 Correct 420 ms 35892 KB Output is correct
9 Correct 346 ms 35852 KB Output is correct
10 Correct 371 ms 35884 KB Output is correct
11 Correct 351 ms 36084 KB Output is correct
12 Correct 342 ms 35820 KB Output is correct
13 Correct 325 ms 35892 KB Output is correct
14 Correct 317 ms 35884 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 3 ms 4556 KB Output is correct
21 Correct 55 ms 11476 KB Output is correct
22 Correct 2 ms 4564 KB Output is correct
23 Correct 3 ms 4652 KB Output is correct
24 Correct 53 ms 11480 KB Output is correct
25 Correct 49 ms 11364 KB Output is correct
26 Correct 56 ms 11508 KB Output is correct
27 Correct 52 ms 11624 KB Output is correct
28 Correct 90 ms 12992 KB Output is correct
29 Correct 726 ms 41520 KB Output is correct
30 Correct 96 ms 12988 KB Output is correct
31 Correct 733 ms 41748 KB Output is correct
32 Correct 428 ms 41216 KB Output is correct
33 Correct 411 ms 41540 KB Output is correct
34 Correct 617 ms 41716 KB Output is correct
35 Correct 1 ms 4444 KB Output is correct
36 Correct 1 ms 4440 KB Output is correct
37 Correct 45 ms 9040 KB Output is correct
38 Correct 385 ms 40256 KB Output is correct
39 Correct 500 ms 40760 KB Output is correct
40 Incorrect 649 ms 41216 KB Output isn't correct
41 Halted 0 ms 0 KB -