Submission #1050986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050986		TahirAliyev	Comparing Plants (IOI20_plants)	C++17	0 / 100	28 ms	13148 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ll long long
#define oo 1e9

const int MAX = 2e5 + 5;

struct ST{
	pii tree[4 * MAX]; 
	int lazy[4 * MAX];
	pii comb(pii a, pii b){
		if(a.first < b.first) return a;
		return b;
	}
	void relax(int node, int l, int r){
		tree[node].first += lazy[node];
		if(l != r){
			lazy[2 * node] += lazy[node];
			lazy[2 * node + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
	void update(int node, int l, int r, int ul, int ur, int val){
		relax(node, l, r);
		if(ur < l || r < ul) return;
		if(ul <= l && r <= ur){
			lazy[node] += val;
			relax(node, l, r);
			return;
		}
		int mid = (l + r) / 2;
		update(2 * node, l, mid, ul, ur, val);
		update(2 * node + 1, mid + 1, r, ul, ur, val);
		tree[node] = comb(tree[2 * node], tree[2 * node + 1]);
	}
	pii ask(int node, int l, int r, int ql, int qr){
		if(qr < l || r < ql) return {oo, 0};
		relax(node, l, r);
		if(ql <= l && r <= qr) return tree[node];
		int mid = (l + r) / 2;
		return comb(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
	}
};

int n;
ST st;
set<int> s;
set<pii> dif;
int id[MAX];
void update(int l, int r, int val){
	if(r < l){
		st.update(1, 0, n - 1, l, n - 1, val);
		st.update(1, 0, n - 1, 1, r, val);
	}
	else st.update(1, 0, n - 1, l, r, val);
}

void add(int i){
	if(!s.size()){
		s.insert(i);
		dif.insert({0, i});
		return;
	}
	s.insert(i);
	auto itr = s.find(i);
	auto prv = itr, nxt = itr;
	if(itr == s.begin()) prv = --s.end();
	else prv = prev(itr);
	if(itr == prev(s.end())) nxt = s.begin();
	else nxt = next(itr);
	dif.erase({(*nxt - *prv + n) % n, *nxt});
	dif.insert({(*nxt - *itr + n) % n, *nxt});
	dif.insert({(*itr - *prv + n) % n, *itr});
}

void rem(int i){
	if(s.size() == 1){
		s.erase(i);
		return;
	}
	auto itr = s.find(i);
	auto prv = itr, nxt = itr;
	if(itr == s.begin()) prv = --s.end();
	else prv = prev(itr);
	if(itr == prev(s.end())) nxt = s.begin();
	else nxt = next(itr);
	dif.insert({(*nxt - *prv + n) % n, *nxt});
	dif.erase({(*nxt - *itr + n) % n, *nxt});
	dif.erase({(*itr - *prv + n) % n, *itr});
	s.erase(i);
}

void init(int k, vector<int> r) {
	n = r.size();
	r.insert(r.begin(), 0);
	for(int i = 0; i < n; i++){
		st.update(1, 0, n - 1, i, i, r[i]);
		if(!r[i]) s.insert(i);
	}
	int pr = -1;
	for(int a : s){
		if(pr != -1) dif.insert({a - pr, a});
		pr = a;
	}
	dif.insert({(*s.begin() - *s.rbegin() + n) % n, *s.begin()});
	int t = n;
	while(s.size()){
		int f = dif.rbegin()->second;
		if(dif.rbegin()->first < k && dif.rbegin()->first){
			rem(f);
			continue;
		}
		rem(f);
		int l = f - k + 1;
		if(l <= 0) l += n;
		id[f] = t--;
		update(l, f - 1, -1);
		while(st.ask(1, 0, n - 1, 0, n - 1).first == 0){
			int a = st.ask(1, 0, n - 1, 0, n - 1).second;
			update(a, a, oo);
			add(a);
		}
	}
}

int compare_plants(int x, int y) {
	x++, y++;
	if(id[x] > id[y]) return 1;
	else return -1;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25