oj.uz

Submission #984112

# Submission time Handle Problem Language Result Execution time Memory
984112 2024-05-16T10:14:34 Z phoenix0423 Comparing Plants (IOI20_plants) C++17
5 / 100
 4000 ms 34384 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]);
	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 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 4444 KB Output is correct
6 Correct 38 ms 7372 KB Output is correct
7 Correct 67 ms 10676 KB Output is correct
8 Correct 340 ms 34296 KB Output is correct
9 Correct 349 ms 34384 KB Output is correct
10 Correct 337 ms 34328 KB Output is correct
11 Correct 340 ms 34340 KB Output is correct
12 Correct 350 ms 34116 KB Output is correct
13 Correct 332 ms 34368 KB Output is correct
14 Correct 334 ms 34232 KB Output is correct

Subtask #2
0 / 14.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 Execution timed out 4091 ms 4444 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 Execution timed out 4091 ms 4444 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Execution timed out 4062 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 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 Execution timed out 4088 ms 4444 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 Incorrect 2 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 4444 KB Output is correct
6 Correct 38 ms 7372 KB Output is correct
7 Correct 67 ms 10676 KB Output is correct
8 Correct 340 ms 34296 KB Output is correct
9 Correct 349 ms 34384 KB Output is correct
10 Correct 337 ms 34328 KB Output is correct
11 Correct 340 ms 34340 KB Output is correct
12 Correct 350 ms 34116 KB Output is correct
13 Correct 332 ms 34368 KB Output is correct
14 Correct 334 ms 34232 KB Output is correct
15 Correct 2 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Execution timed out 4091 ms 4444 KB Time limit exceeded
18 Halted 0 ms 0 KB -