oj.uz

Submission #1052672

# Submission time Handle Problem Language Result Execution time Memory
1052672 2024-08-10T18:55:35 Z TahirAliyev Comparing Plants (IOI20_plants) C++17
44 / 100
 283 ms 35384 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define oo 1e9
	
const int MAX = 2e5 + 5;

struct ST{
	pii tree[4 * MAX]; 
	int lazy[4 * MAX];
	void build(int node, int l, int r){
		if(l == r){
			tree[node] = {0, l};
			return;
		}
		int mid = (l + r) / 2;
		build(2 * node, l, mid);
		build(2 * node + 1, mid + 1, r);
		tree[node] = min(tree[2 * node], tree[2 * node + 1]);
	}
	void relax(int node, int l, int r){
		tree[node].first += lazy[node];
		if(l != r){
			lazy[2 * node] += lazy[node];
			lazy[2 * node + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
	void update(int node, int l, int r, int ul, int ur, int val){
		relax(node, l, r);
		if(ur < l || r < ul) return;
		if(ul <= l && r <= ur){
			lazy[node] += val;
			relax(node, l, r);
			return;
		}
		int mid = (l + r) / 2;
		update(2 * node, l, mid, ul, ur, val);
		update(2 * node + 1, mid + 1, r, ul, ur, val);
		tree[node] = min(tree[2 * node], tree[2 * node + 1]);
	}
	pii ask(int node, int l, int r, int ql, int qr){
		if(qr < l || r < ql) return {oo + 9, oo};
		relax(node, l, r);
		if(ql <= l && r <= qr) return tree[node];
		int mid = (l + r) / 2;
		return min(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
	}
};
	
int n;
ST st;
set<int> s;
set<pii> dif;
int id[MAX];
void update(int l, int r, int val){
	if(r < l){
		st.update(1, 0, n - 1, l, n - 1, val);
		st.update(1, 0, n - 1, 0, r, val);
	}
	else st.update(1, 0, n - 1, l, r, val);
}
	
void add(int i){
	if(!s.size()){
		s.insert(i);
		dif.insert({0, i});
		return;
	}
	s.insert(i);
	auto itr = s.find(i);
	auto prv = itr, nxt = itr;
	if(itr == s.begin()) prv = --s.end();
	else prv = prev(itr);
	if(itr == --s.end()) nxt = s.begin();
	else nxt = next(itr);
	dif.erase({(*nxt - *prv + n) % n, *nxt});
	dif.insert({(*nxt - *itr + n) % n, *nxt});
	dif.insert({(*itr - *prv + n) % n, *itr});
}
	
void rem(int i){
	if(s.size() == 1){
		s.erase(i);
		dif.erase({0, i});
		return;
	}
	auto itr = s.find(i);
	auto prv = itr, nxt = itr;
	if(itr == s.begin()) prv = --s.end();
	else prv = prev(itr);
	if(itr == --s.end()) nxt = s.begin();
	else nxt = next(itr);
	dif.erase({(*nxt - *itr + n) % n, *nxt});
	dif.erase({(*itr - *prv + n) % n, *itr});
	dif.insert({(*nxt - *prv + n) % n, *nxt});
	s.erase(i);
}
	
void init(int k, vector<int> r) {
	n = r.size();
	st.build(1, 0, n - 1);
	for(int i = 0; i < n; i++){
		if(!r[i]){
			s.insert(i);
			update(i, i, oo);
		} 
		else update(i, i, r[i]);
	}
	for(auto itr = s.begin(); itr != s.end(); itr++){
		dif.insert({(*itr - ((itr != s.begin())? *prev(itr) : *s.rbegin()) + n) % n, *itr});
	}
	int t = n;
	while(s.size()){
		int f = dif.rbegin()->second;
		if(dif.rbegin()->first < k && dif.rbegin()->first){
			rem(f);
			continue;
		}
		rem(f);
		int l = (f - k + 1 + n) % n;
		id[f] = t--;
		update(l, (f - 1 + n) % n, -1);
		// cout << st.ask(1, 0, n - 1, 0, n - 1).first << '\n';
		while(st.ask(1, 0, n - 1, 0, n - 1).first == 0){
			int a = st.ask(1, 0, n - 1, 0, n - 1).second;
			// cout << a << ' ';
			update(a, a, oo);
			add(a);
		}
	}
}
	
int compare_plants(int x, int y) {
	if(id[x] > id[y]) return 1;
	else return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Incorrect 1 ms 8540 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 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8752 KB Output is correct
7 Correct 31 ms 13216 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 35 ms 13300 KB Output is correct
11 Correct 34 ms 13436 KB Output is correct
12 Correct 29 ms 13392 KB Output is correct
13 Correct 35 ms 13396 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8752 KB Output is correct
7 Correct 31 ms 13216 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 35 ms 13300 KB Output is correct
11 Correct 34 ms 13436 KB Output is correct
12 Correct 29 ms 13392 KB Output is correct
13 Correct 35 ms 13396 KB Output is correct
14 Correct 53 ms 13908 KB Output is correct
15 Correct 260 ms 16980 KB Output is correct
16 Correct 46 ms 13904 KB Output is correct
17 Correct 231 ms 17132 KB Output is correct
18 Correct 283 ms 26192 KB Output is correct
19 Correct 167 ms 17064 KB Output is correct
20 Correct 214 ms 17224 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 28 ms 13048 KB Output is correct
4 Correct 194 ms 22612 KB Output is correct
5 Correct 237 ms 17748 KB Output is correct
6 Correct 252 ms 16756 KB Output is correct
7 Correct 255 ms 16772 KB Output is correct
8 Correct 243 ms 16896 KB Output is correct
9 Correct 221 ms 21076 KB Output is correct
10 Correct 231 ms 17920 KB Output is correct
11 Correct 219 ms 35384 KB Output is correct
12 Correct 144 ms 16468 KB Output is correct
13 Correct 263 ms 29524 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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