oj.uz

Submission #832477

# Submission time Handle Problem Language Result Execution time Memory
832477 2023-08-21T10:45:59 Z penguinman Comparing Plants (IOI20_plants) C++17
70 / 100
 1561 ms 51544 KB 
#include "plants.h"
#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

constexpr ll inf = (1ll<<60);

template<typename T = pii, typename S = ll>
struct lazy_segment_tree{
	int N, log;
	T valINF;
	S lazyINF;
	vector<T> node;
	vector<S> lazy;
	lazy_segment_tree(int n, T valINF_, S lazyINF_): valINF(valINF_), lazyINF(lazyINF_){
		N = 1;
		log = 1;
		while(N <= n){
			N *= 2;
			log++;
		}
		node.resize(2*N, valINF);
		lazy.resize(2*N, lazyINF);
	}
	void init(vector<T> a){
		rep(i,0,a.size()) node[i+N] = a[i];
		per(i,N-1,1) node[i] = compare(node[i*2], node[i*2+1]);
	}
	void range_add(S val, ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
		if(r == -1) r = N;
		eval(now);
		if(r <= a || b <= l) return;
		if(a <= l && r <= b){
			addition(lazy[now], val);
			eval(now);
			return;
		}
		range_add(val, a, b, now*2, l, (l+r)/2);
		range_add(val, a, b, now*2+1, (l+r)/2, r);
		node[now] = compare(node[now*2], node[now*2+1]);
	}
	T calc(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
		if(r == -1) r = N;
		eval(now);
		if(r <= a || b <= l) return valINF;
		if(a <= l && r <= b) return node[now];
		T L = calc(a, b, now*2, l, (l+r)/2);
		T R = calc(a, b, now*2+1, (l+r)/2, r);
		return compare(L,R);
	}
	void update(ll idx, T val){
		ll now = idx+N;
		per(i,log,0){
			eval(now>>i);
		}
		node[now] = val;
		now /= 2;
		while(now){
			eval(now*2);
			eval(now*2+1);
			node[now] = compare(node[now*2], node[now*2+1]);
			now /= 2;
		}
	}
	void eval(ll now){
		addition(node[now], lazy[now]);
		if(now < N){
			addition(lazy[now*2], lazy[now]);
			addition(lazy[now*2+1], lazy[now]);
		}
		lazy[now] = lazyINF;
	}
	void addition(T &a, S b){
		a.first += b;
	}
	void addition(S &a, S b){
		a += b;
	}
	T compare(T a, T b){
		return std::min(a, b);
	}
};


ll N;
vi height;

void subtask_2_3(int k, vector<int> r){
	N = r.size();
	lazy_segment_tree<pii, ll> seg(N, mp(inf,0), 0);
	{
		vector<pii> a(N);
		rep(i,0,N) a[i] = mp(r[i], i);
		seg.init(a);
	}
	height.resize(N);
	ll now = N;

	std::set<ll> cand;

	std::set<ll> top;

	auto check = [&](ll idx){
		auto itr = cand.lower_bound(idx);
		itr--;
		ll right = idx+k-1;
		right -= N;
		if(*itr <= right) return true;
		else return false;
	};

	while(true){
		while(true){
			auto el = seg.calc(0,N);
			if(el.first) break;
			ll i = el.second;
			cand.insert(i);
			cand.insert(i-N);
			cand.insert(i+N);
			if(check(i)) top.insert(i);
			if(cand.size() > 3){
				ll upper = *cand.upper_bound(i);
				if(upper >= N) upper -= N;
				if(top.count(upper)){
					if(!check(upper)) top.erase(upper);
				}
			}
			seg.update(i,mp(inf, 0));
		}
		if(cand.empty()) break;
		assert(top.size() == 1);
		ll t = *top.begin();
		height[t] = now--;
		{
			ll l = t-k+1;
			ll r = t;
			if(0 <= l) seg.range_add(-1, l, r);
			else{
				seg.range_add(-1, 0, r);
				seg.range_add(-1, N+l, N);
			}
		}
		cand.erase(t);
		cand.erase(t-N);
		cand.erase(t+N);
		top.erase(t);
		if(cand.empty()) continue;
		ll upper = *cand.upper_bound(t);
		if(upper >= N) upper -= N;
		if(check(upper)) top.insert(upper);
	}

	/*while((seg.calc(0,N)).first == 0){
		vi idx;
		while(true){
			auto el = seg.calc(0,N);
			if(el.first) break;
			idx.pb(el.second);
			seg.update(el.second, mp(inf, 0));
		}
		if(idx.size() == 1){
			height[idx[0]] = now--;
			ll l = idx[0]-k+1;
			ll r = idx[0];
			if(0 <= l) seg.range_add(-1, l, r);
			else{
				seg.range_add(-1, 0, r);
				seg.range_add(-1, N+l, N);
			}
			continue;
		}
		assert(idx.size() == 2);
		if(idx[0] > idx[1]) std::swap(idx[0], idx[1]);
		if(idx[1] < idx[0]+k){
			idx[0] = now--;
			idx[1] = now--;
		}
		else{
			idx[1] = now--;
			idx[0] = now--;
		}
		rep(i,0,2){
			ll l = idx[i]-k+1;
			ll r = idx[i];
			if(0 <= l) seg.range_add(-1, l, r);
			else{
				seg.range_add(-1, 0, r);
				seg.range_add(-1, N+l, N);
			}
		}
	}*/
	/*rep(i,0,N) cout << height[i] << " ";
	cout << ln;*/
}

vii edge;

void subtask_5(int k, std::vector<int> r){
	N = r.size();
	edge.resize(N,vi(N));
	vector<bool> flag(N);
	rep(_,0,N){
		ll top = -1;
		rep(i,0,N){
			if(r[i]) continue;
			ll now = i;
			bool f = true;
			rep(j,1,k){
				now--;
				if(now < 0) now += N;
				if(r[now]) continue;
				f = false;
			}
			if(f) top = i;
		}
		flag[top] = true;
		/*cout << top << ln;
		rep(i,0,N) cout << r[i] << " ";
		cout << ln;*/
		ll now = top;
		rep(j,1,k){
			now++;
			now %= N;
			if(flag[now]) continue;
			edge[top][now] = true;
		}
		now = top;
		rep(j,1,k){
			now--;
			if(now < 0) now += N;
			r[now]--;
			if(flag[now]) continue;
			edge[top][now] = true;
		}
		r[top] = 1e9;
	}
	rep(k,0,N){
		rep(i,0,N){
			rep(j,0,N){
				edge[i][j] |= (edge[i][k]&edge[k][j]);
			}
		}
	}
}

vii par;
vector<int> r_mem;

void subtask_1(int k, std::vector<int> r){
	N = r.size();
	par.resize(N);
	rep(i,0,N){
		if(r[i] == 0){
			par[(i+1)%N].pb(i);
		}
		else{
			par[i].pb((i+1)%N);
		}
	}
	r_mem = r;
}

vi answer;
bool is_6 = false;

void subtask_4_6(int k, vector<int> r){
	is_6 = true;
	answer.resize(N);
	{
		auto rrr = r;
		N = r.size();
		lazy_segment_tree<pii, ll> seg(N, mp(inf,0), 0);
		{
			vector<pii> a(N);
			rep(i,0,N) a[i] = mp(r[i], i);
			seg.init(a);
		}
		height.resize(N);
		ll now = N;

		std::set<ll> cand;

		std::set<ll> top;

		auto check = [&](ll idx){
			auto itr = cand.lower_bound(idx);
			itr--;
			if(idx-*itr <= k-1) return false;
			else return true;
		};

		vi ord;

		while(true){
			while(true){
				auto el = seg.calc(0,N);
				if(el.first) break;
				ll i = el.second;
				cand.insert(i);
				cand.insert(i-N);
				cand.insert(i+N);
				if(check(i)) top.insert(i);
				if(cand.size() > 3){
					ll upper = *cand.upper_bound(i);
					if(upper >= N) upper -= N;
					if(top.count(upper)){
						if(!check(upper)) top.erase(upper);
					}
				}
				seg.update(i,mp(inf, 0));
			}
			if(cand.empty()) break;
			ll t = *top.begin();
			height[t] = now--;
			ord.pb(t);
			{
				ll l = t-k+1;
				ll r = t;
				if(0 <= l) seg.range_add(-1, l, r);
				else{
					seg.range_add(-1, 0, r);
					seg.range_add(-1, N+l, N);
				}
			}
			cand.erase(t);
			cand.erase(t-N);
			cand.erase(t+N);
			top.erase(t);
			if(cand.empty()) continue;
			ll upper = *cand.upper_bound(t);
			if(upper >= N) upper -= N;
			if(check(upper)) top.insert(upper);
		}
		r = rrr;

		std::set<ll> remain;
		rep(i,0,N) remain.insert(i), remain.insert(i+N), remain.insert(i-N);
		vector<bool> flag(N);
		flag[0] = true;
		for(auto i: ord){
			if(remain.count(i)){
				remain.erase(i);
				remain.erase(i+N);
				remain.erase(i-N);
			}
			if(!flag[i]) continue;
			while(true){
				auto itr = remain.upper_bound(i);
				if(itr == remain.end()) break;
				if(*itr-i > k-1) break;
				ll now = *itr;
				now %= N;
				flag[now] = true;
				remain.erase(now);
				remain.erase(now+N);
				remain.erase(now-N);
			}
			while(true){
				auto itr = remain.lower_bound(i);
				if(itr == remain.begin()) break;
				itr--;
				if(i-*itr > k-1) break;
				ll now = *itr;
				now %= N;
				if(now < 0) now += N;
				flag[now] = true;
				remain.erase(now);
				remain.erase(now+N);
				remain.erase(now-N);
			}
		}
		rep(i,0,N){
			if(flag[i]) answer[i] = 1;
		}
	}

	{
		auto rrr = r;
		rep(i,0,N) r[i] = k-1-r[i];
		lazy_segment_tree<pii, ll> seg(N, mp(inf,0), 0);
		{
			vector<pii> a(N);
			rep(i,0,N) a[i] = mp(r[i], i);
			seg.init(a);
		}
		height.resize(N);
		ll now = N;

		std::set<ll> cand;

		std::set<ll> top;

		auto check = [&](ll idx){
			auto itr = cand.lower_bound(idx);
			itr--;
			if(idx-*itr <= k-1) return false;
			else return true;
		};

		vi ord;

		while(true){
			while(true){
				auto el = seg.calc(0,N);
				if(el.first) break;
				ll i = el.second;
				cand.insert(i);
				cand.insert(i-N);
				cand.insert(i+N);
				if(check(i)) top.insert(i);
				if(cand.size() > 3){
					ll upper = *cand.upper_bound(i);
					if(upper >= N) upper -= N;
					if(top.count(upper)){
						if(!check(upper)) top.erase(upper);
					}
				}
				seg.update(i,mp(inf, 0));
			}
			if(cand.empty()) break;
			ll t = *top.begin();
			ord.pb(t);
			{
				ll l = t-k+1;
				ll r = t;
				if(0 <= l) seg.range_add(-1, l, r);
				else{
					seg.range_add(-1, 0, r);
					seg.range_add(-1, N+l, N);
				}
			}
			cand.erase(t);
			cand.erase(t-N);
			cand.erase(t+N);
			top.erase(t);
			if(cand.empty()) continue;
			ll upper = *cand.upper_bound(t);
			if(upper >= N) upper -= N;
			if(check(upper)) top.insert(upper);
		}
		r = rrr;

		std::set<ll> remain;
		rep(i,0,N) remain.insert(i), remain.insert(i+N), remain.insert(i-N);
		vector<bool> flag(N);
		flag[0] = true;
		for(auto i: ord){
			if(remain.count(i)){
				remain.erase(i);
				remain.erase(i+N);
				remain.erase(i-N);
			}
			if(!flag[i]) continue;
			while(true){
				auto itr = remain.upper_bound(i);
				if(itr == remain.end()) break;
				if(*itr-i > k-1) break;
				ll now = *itr;
				now %= N;
				flag[now] = true;
				remain.erase(now);
				remain.erase(now+N);
				remain.erase(now-N);
			}
			while(true){
				auto itr = remain.lower_bound(i);
				if(itr == remain.begin()) break;
				itr--;
				if(i-*itr > k-1) break;
				ll now = *itr;
				now %= N;
				if(now < 0) now += N;
				flag[now] = true;
				remain.erase(now);
				remain.erase(now+N);
				remain.erase(now-N);
			}
		}
		rep(i,0,N){
			if(flag[i]) answer[i] = -1;
		}
	}
}

void init(int k, std::vector<int> r) {
	N = r.size();
	if(N <= 300) subtask_5(k,r);
	else if(2*k > N) subtask_2_3(k,r);
	else subtask_4_6(k,r);
}

int compare_plants(int x, int y) {
	if(!height.empty()){
		if(x == 0 && is_6) return answer[y];
		if(height[x] < height[y]) return -1;
		else return 1;
	}
	else if(!edge.empty()){
		if(edge[x][y]) return 1;
		else if(edge[y][x]) return -1;
		else return 0;
	}
	else{
		std::function<ll(ll)> root = [&](ll now){
			if(par[now].empty()) return now;
			return par[now][0] = root(par[now][0]);	
		};
		if(par[x].size() == 2 && par[y].size() == 2) return 0;
		if(par[x].empty() && par[y].empty()) return 0;
		if(par[x].size() == 2){
			if(root(par[x][0]) == root(y)) return -1;
			if(root(par[x][1]) == root(y)) return -1;
			return 0;
		}
		if(par[y].size() == 2){
			if(root(par[y][0]) == root(x)) return 1;
			if(root(par[y][1]) == root(x)) return 1;
			return 0;
		}
		if(root(x) != root(y)) return 0;
		if(r_mem[x] == 0 && r_mem[(y+N-1)%N] == 0) return 1;
		if(r_mem[y] == 0 && r_mem[(x+N-1)%N] == 0) return -1;
		if(r_mem[x] == 1 && r_mem[(y+1)%N] == 1) return -1;
		if(r_mem[y] == 1 && r_mem[(x+1)%N] == 1) return 1;
	}
}

Compilation message

plants.cpp: In function 'void subtask_4_6(int, std::vector<int>)':
plants.cpp:404:6: warning: unused variable 'now' [-Wunused-variable]
  404 |   ll now = N;
      |      ^~~
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:543:1: warning: control reaches end of non-void function [-Wreturn-type]
  543 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 38 ms 2984 KB Output is correct
7 Incorrect 123 ms 8308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 45 ms 3356 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 45 ms 3372 KB Output is correct
11 Correct 46 ms 3540 KB Output is correct
12 Correct 42 ms 3540 KB Output is correct
13 Correct 45 ms 3448 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 45 ms 3356 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 45 ms 3372 KB Output is correct
11 Correct 46 ms 3540 KB Output is correct
12 Correct 42 ms 3540 KB Output is correct
13 Correct 45 ms 3448 KB Output is correct
14 Correct 69 ms 4948 KB Output is correct
15 Correct 422 ms 23528 KB Output is correct
16 Correct 68 ms 5048 KB Output is correct
17 Correct 473 ms 23532 KB Output is correct
18 Correct 567 ms 32912 KB Output is correct
19 Correct 303 ms 23512 KB Output is correct
20 Correct 413 ms 23536 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 45 ms 3484 KB Output is correct
4 Correct 956 ms 51496 KB Output is correct
5 Correct 1112 ms 51436 KB Output is correct
6 Correct 1342 ms 51412 KB Output is correct
7 Correct 1561 ms 51484 KB Output is correct
8 Correct 1440 ms 51440 KB Output is correct
9 Correct 1042 ms 51480 KB Output is correct
10 Correct 1079 ms 51472 KB Output is correct
11 Correct 1049 ms 51484 KB Output is correct
12 Correct 1114 ms 51464 KB Output is correct
13 Correct 1166 ms 51416 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 30 ms 1560 KB Output is correct
8 Correct 29 ms 1560 KB Output is correct
9 Correct 29 ms 1552 KB Output is correct
10 Correct 29 ms 1624 KB Output is correct
11 Correct 29 ms 1556 KB Output is correct
12 Correct 36 ms 1552 KB Output is correct
13 Correct 32 ms 1552 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 1110 ms 51356 KB Output is correct
7 Correct 1196 ms 51544 KB Output is correct
8 Correct 1364 ms 51388 KB Output is correct
9 Correct 1367 ms 51484 KB Output is correct
10 Correct 924 ms 51496 KB Output is correct
11 Correct 1117 ms 51544 KB Output is correct
12 Correct 958 ms 51488 KB Output is correct
13 Correct 1131 ms 51460 KB Output is correct
14 Correct 1368 ms 51480 KB Output is correct
15 Correct 1437 ms 51484 KB Output is correct
16 Correct 1086 ms 51148 KB Output is correct
17 Correct 1149 ms 51428 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 38 ms 2984 KB Output is correct
7 Incorrect 123 ms 8308 KB Output isn't correct
8 Halted 0 ms 0 KB -