oj.uz

Submission #984110

# Submission time Handle Problem Language Result Execution time Memory
984110 2024-05-16T10:13:04 Z phoenix0423 Comparing Plants (IOI20_plants) C++17
5 / 100
 4000 ms 37072 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];
	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]);
	int pos = qry(0, 2 * n - 1).s;
	for(int rd = 0; rd < n; rd++){
		while(true){
			if(pos < n) pos += n;
			pll tmp = qry(pos - k + 1, pos - 1);
			if(!tmp.f) pos = tmp.s;
			else break;
		}
		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 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 Correct 1 ms 4544 KB Output is correct
6 Correct 40 ms 8148 KB Output is correct
7 Correct 67 ms 12716 KB Output is correct
8 Correct 343 ms 36884 KB Output is correct
9 Correct 332 ms 36676 KB Output is correct
10 Correct 334 ms 37072 KB Output is correct
11 Correct 336 ms 36672 KB Output is correct
12 Correct 329 ms 36888 KB Output is correct
13 Correct 310 ms 36672 KB Output is correct
14 Correct 334 ms 36880 KB Output is correct

Subtask #2
0 / 14.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 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Execution timed out 4045 ms 4444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 4440 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4544 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 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 Correct 1 ms 4544 KB Output is correct
6 Correct 40 ms 8148 KB Output is correct
7 Correct 67 ms 12716 KB Output is correct
8 Correct 343 ms 36884 KB Output is correct
9 Correct 332 ms 36676 KB Output is correct
10 Correct 334 ms 37072 KB Output is correct
11 Correct 336 ms 36672 KB Output is correct
12 Correct 329 ms 36888 KB Output is correct
13 Correct 310 ms 36672 KB Output is correct
14 Correct 334 ms 36880 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Incorrect 1 ms 4444 KB Output isn't correct
18 Halted 0 ms 0 KB -