oj.uz

Submission #832385

# Submission time Handle Problem Language Result Execution time Memory
832385 2023-08-21T09:52:09 Z penguinman Comparing Plants (IOI20_plants) C++17
38 / 100
 566 ms 32972 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]);
			}
		}
	}
}

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);
}

int compare_plants(int x, int y) {
	if(!height.empty()){
		if(height[x] < height[y]) return -1;
		else return 1;
	}
	else{
		if(edge[x][y]) return 1;
		else if(edge[y][x]) return -1;
		else return 0;
	}
}

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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 38 ms 3112 KB Output is correct
7 Runtime error 31 ms 5432 KB Execution killed with signal 11
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 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 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 47 ms 3348 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 46 ms 3412 KB Output is correct
11 Correct 45 ms 3604 KB Output is correct
12 Correct 44 ms 3544 KB Output is correct
13 Correct 46 ms 3380 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 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 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 47 ms 3348 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 46 ms 3412 KB Output is correct
11 Correct 45 ms 3604 KB Output is correct
12 Correct 44 ms 3544 KB Output is correct
13 Correct 46 ms 3380 KB Output is correct
14 Correct 79 ms 5048 KB Output is correct
15 Correct 415 ms 23520 KB Output is correct
16 Correct 70 ms 5044 KB Output is correct
17 Correct 406 ms 23536 KB Output is correct
18 Correct 566 ms 32972 KB Output is correct
19 Correct 297 ms 23532 KB Output is correct
20 Correct 455 ms 23528 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 1 ms 212 KB Output is correct
3 Runtime error 29 ms 5088 KB Execution killed with signal 11
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 1 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 1556 KB Output is correct
8 Correct 32 ms 1552 KB Output is correct
9 Correct 28 ms 1564 KB Output is correct
10 Correct 30 ms 1564 KB Output is correct
11 Correct 30 ms 1548 KB Output is correct
12 Correct 29 ms 1568 KB Output is correct
13 Correct 29 ms 1548 KB Output is correct

Subtask #6
0 / 15.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 Runtime error 1 ms 340 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 38 ms 3112 KB Output is correct
7 Runtime error 31 ms 5432 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -