oj.uz

Submission #832278

# Submission time Handle Problem Language Result Execution time Memory
832278 2023-08-21T08:24:10 Z penguinman Comparing Plants (IOI20_plants) C++17
27 / 100
 560 ms 32108 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 init(int k, std::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;*/
}

int compare_plants(int x, int y) {
	if(height[x] < height[y]) return -1;
	else return 1;
}

Subtask #1
0 / 5.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 Runtime error 1 ms 340 KB Execution killed with signal 6
5 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 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 50 ms 3208 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 45 ms 3276 KB Output is correct
11 Correct 45 ms 3416 KB Output is correct
12 Correct 42 ms 3396 KB Output is correct
13 Correct 44 ms 3240 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 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 50 ms 3208 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 45 ms 3276 KB Output is correct
11 Correct 45 ms 3416 KB Output is correct
12 Correct 42 ms 3396 KB Output is correct
13 Correct 44 ms 3240 KB Output is correct
14 Correct 68 ms 4924 KB Output is correct
15 Correct 412 ms 22768 KB Output is correct
16 Correct 67 ms 4940 KB Output is correct
17 Correct 398 ms 22764 KB Output is correct
18 Correct 560 ms 32108 KB Output is correct
19 Correct 289 ms 22764 KB Output is correct
20 Correct 378 ms 22768 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
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 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

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