oj.uz

Submission #832469

# Submission time Handle Problem Language Result Execution time Memory
832469 2023-08-21T10:43:04 Z penguinman Comparing Plants (IOI20_plants) C++17
26 / 100
 1657 ms 54260 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;

void subtask_4_6(int k, vector<int> r){
	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) 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:609:1: warning: control reaches end of non-void function [-Wreturn-type]
  609 | }
      | ^

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 38 ms 3040 KB Output is correct
7 Incorrect 126 ms 8324 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.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 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Runtime error 2 ms 596 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Runtime error 2 ms 596 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

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 47 ms 3576 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 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 2 ms 340 KB Output is correct
7 Correct 29 ms 1548 KB Output is correct
8 Correct 29 ms 1620 KB Output is correct
9 Correct 28 ms 1560 KB Output is correct
10 Correct 29 ms 1548 KB Output is correct
11 Correct 28 ms 1604 KB Output is correct
12 Correct 28 ms 1612 KB Output is correct
13 Correct 29 ms 1612 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 1334 ms 53576 KB Output is correct
7 Correct 1538 ms 54024 KB Output is correct
8 Correct 1585 ms 53976 KB Output is correct
9 Correct 1657 ms 54252 KB Output is correct
10 Correct 1220 ms 53648 KB Output is correct
11 Correct 1361 ms 54260 KB Output is correct
12 Correct 1180 ms 53504 KB Output is correct
13 Correct 1369 ms 53808 KB Output is correct
14 Correct 1533 ms 53912 KB Output is correct
15 Correct 1625 ms 54104 KB Output is correct
16 Correct 1367 ms 53344 KB Output is correct
17 Correct 1385 ms 53684 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 38 ms 3040 KB Output is correct
7 Incorrect 126 ms 8324 KB Output isn't correct
8 Halted 0 ms 0 KB -