oj.uz

Submission #832470

# Submission time Handle Problem Language Result Execution time Memory
832470 2023-08-21T10:43:50 Z penguinman Comparing Plants (IOI20_plants) C++17
53 / 100
 1690 ms 51548 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();
			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);
		}
		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;
	}
}

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 'int compare_plants(int, int)':
plants.cpp:611:1: warning: control reaches end of non-void function [-Wreturn-type]
  611 | }
      | ^

Subtask #1
0 / 5.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 0 ms 212 KB Output is correct
6 Correct 36 ms 3048 KB Output is correct
7 Incorrect 126 ms 8316 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 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 54 ms 3408 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 51 ms 3416 KB Output is correct
11 Correct 44 ms 3500 KB Output is correct
12 Correct 42 ms 3500 KB Output is correct
13 Correct 44 ms 3416 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 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 54 ms 3408 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 51 ms 3416 KB Output is correct
11 Correct 44 ms 3500 KB Output is correct
12 Correct 42 ms 3500 KB Output is correct
13 Correct 44 ms 3416 KB Output is correct
14 Correct 69 ms 5040 KB Output is correct
15 Correct 427 ms 23548 KB Output is correct
16 Correct 71 ms 5048 KB Output is correct
17 Correct 430 ms 23536 KB Output is correct
18 Correct 566 ms 32968 KB Output is correct
19 Correct 289 ms 23500 KB Output is correct
20 Correct 396 ms 23564 KB Output is correct

Subtask #4
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 Incorrect 45 ms 3604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.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 0 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 28 ms 1548 KB Output is correct
8 Correct 33 ms 1560 KB Output is correct
9 Correct 28 ms 1548 KB Output is correct
10 Correct 28 ms 1556 KB Output is correct
11 Correct 28 ms 1564 KB Output is correct
12 Correct 28 ms 1552 KB Output is correct
13 Correct 29 ms 1664 KB Output is correct

Subtask #6
15.0 / 15.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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 5 ms 536 KB Output is correct
6 Correct 1317 ms 51540 KB Output is correct
7 Correct 1565 ms 51480 KB Output is correct
8 Correct 1690 ms 51480 KB Output is correct
9 Correct 1630 ms 51372 KB Output is correct
10 Correct 1245 ms 51508 KB Output is correct
11 Correct 1418 ms 51460 KB Output is correct
12 Correct 1234 ms 51408 KB Output is correct
13 Correct 1348 ms 51472 KB Output is correct
14 Correct 1540 ms 51548 KB Output is correct
15 Correct 1634 ms 51400 KB Output is correct
16 Correct 1353 ms 51152 KB Output is correct
17 Correct 1303 ms 51424 KB Output is correct

Subtask #7
0 / 25.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 0 ms 212 KB Output is correct
6 Correct 36 ms 3048 KB Output is correct
7 Incorrect 126 ms 8316 KB Output isn't correct
8 Halted 0 ms 0 KB -