Submission #1050820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050820		TahirAliyev	Comparing Plants (IOI20_plants)	C++17	0 / 100	4085 ms	10844 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;
int id[MAX];

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;
void update(int l, int r, int val){
	if(r < l){
		st.update(1, 1, n, l, n, val);
		st.update(1, 1, n, 1, r, val);
	}
	else st.update(1, 1, n, l, r, val);
}

void add(int i){
	if(!s.size()){
		s.insert(i);
		dif.insert({n, i});
		return;
	}
	auto itr = s.lower_bound(i);
	if(itr == s.begin()) dif.insert({n - (*s.rbegin() - i), i});
	else dif.insert({i - *prev(itr), i});
	if(itr == s.end()){
		dif.erase({n - (*s.rbegin() - *s.begin()), *s.begin()});
		dif.insert({n - (i - *s.begin()), *s.begin()});
	} 
	else{
		dif.erase({*itr - *prev(itr), *itr});
		dif.insert({*itr - i, *itr});
	}
	s.insert(i);
}

void rem(int i){
	s.erase(i);
	if(!s.size()) return;
	auto itr = s.lower_bound(i);
	if(itr == s.begin()) dif.erase({n - (*s.rbegin() - i), i});
	else dif.erase({i - *prev(itr), i});
	if(itr == s.end()){
		dif.erase({n - (i - *s.begin()), *s.begin()});
		dif.insert({n - (*s.rbegin() - *s.begin()), *s.begin()});
	} 
	else{
		dif.erase({*itr - i, *itr});
		dif.insert({*itr - *prev(itr), *itr});
	}
}

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