Submission #984144

#	Time	Username	Problem	Language	Result	Execution time	Memory
984144		phoenix0423	Comparing Plants (IOI20_plants)	C++17	32 / 100	682 ms	38148 KiB

plants

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int maxn = 4e5 + 5;
const int INF = 1e9;
#include "plants.h"

int a[maxn], rk[maxn];
int n, k;
vector<int> r;
pll st[maxn * 4];
ll tag[maxn * 4];

void cast(int v, int val){
	st[v].f += val, tag[v] += val;
}

void push(int v){
	if(tag[v]){
		cast(v * 2, tag[v]);
		cast(v * 2 + 1, tag[v]);
		tag[v] = 0;
	}
}

void upd(int l, int r, int val, int v = 1, int L = 0, int R = 2 * n - 1){
    if(l > R || r < L) return;
	if(L == R) st[v].s = L;
    if(l <= L && r >= R){
        st[v].f += val;
        tag[v] += val;
        return;
    }
    push(v);
	int m = (L + R) / 2;
	upd(l, r, val, v * 2, L, m);
	upd(l, r, val, v * 2 + 1, m + 1, R);
	st[v] = min(st[v * 2], st[v * 2 + 1]);
}

pll qry(int l, int r, int v = 1, int L = 0, int R = 2 * n - 1){
	if(l > R || r < L) return {INF, 0};
	if(l <= L && r >= R) return st[v];
	push(v);
	int m = (L + R) / 2;
	return min(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}

void init(int _k, std::vector<int> _r) {
	r = _r, k = _k;
	n = r.size();
	for(auto x : _r) r.pb(x);
	{
		for(int i = 0; i < 2 * n; i++) a[i] = 1 - r[i] * 2;
		for(int i = 1; i < 2 * n; i++) a[i] += a[i - 1];
	}
	for(int i = 0; i < 2 * n; i++) upd(i, i, r[i]);
	stack<int> stk;
	vector<int> used(2 * n + 1);
	for(int rd = 0; rd < n; rd++){
		if(stk.empty()) stk.push(qry(0, 2 * n - 1).s);
		while(true){
			int pos = stk.top();
			if(pos < n) pos += n;
			pll tmp = qry(pos - k + 1, pos - 1);
			if(!tmp.f){
				assert(!used[tmp.s]);
				pos = tmp.s, stk.push(pos);
				used[tmp.s] = 1;
			}
			else break;
		}
		int pos = stk.top(); stk.pop();
		pos %= n;
		rk[pos] = rd;
		upd(pos, pos, INF), upd(pos + n, pos + n, INF);
		upd(max(0, pos - k + 1), pos - 1, -1);
		pos += n;
		upd(pos - k + 1, pos - 1, -1);
	}
}

int compare_plants(int x, int y) {
	if(k <= 2){
		int m = a[y - 1] - (x ? a[x - 1] : 0);
		if(m == y - x) return 1;
		if(m == x - y) return -1;
		x += n;
		m = a[x - 1] - a[y - 1];
		if(m == x - y) return -1;
		if(m == y - x) return 1;
		return 0;
	}
	return rk[x] < rk[y] ? 1 : -1;
}

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