제출 #826328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
826328		NothingXD	식물 비교 (IOI20_plants)	C++17	100 / 100	1615 ms	85272 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;
const int lg = 20;
const int inf = 1e6;

int n, k, a[maxn], idx[maxn], ver[maxn], seg[maxn << 2][3], lazy[maxn << 2][3];
ll par[2][maxn][lg];

void shift(int v, int x, int l, int r);

void add(int v, int x, int l, int r, int ql, int qr, int val){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		seg[v][x] += val;
		lazy[v][x] += val;
		return;
	}
	shift(v, x, l, r);
	int mid = (l + r) >> 1;
	add(v << 1, x, l, mid, ql, qr, val);
	add(v << 1 | 1, x, mid, r, ql, qr, val);
	seg[v][x] = min(seg[v<<1][x], seg[v<<1|1][x]);
}

int find0(int v, int x, int l, int r){
	if (seg[v][x] != 0) return -1;
	if (l + 1 == r) return l;
	shift(v, x, l, r);
	int mid = (l + r) >> 1;
	int res = find0(v << 1, x, l, mid);
	if (res == -1) return find0(v << 1 | 1, x, mid, r);
	return res;
}

void shift(int v, int x, int l, int r){
	if (lazy[v][x] == 0) return;
	int mid = (l + r) >> 1;
	add(v << 1, x, l, mid, l, mid, lazy[v][x]);
	add(v << 1 | 1, x, mid, r, mid, r, lazy[v][x]);
	lazy[v][x] = 0;
}

int get(int v, int x, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return inf;
	if (ql <= l && r <= qr) return seg[v][x];
	shift(v, x, l, r);
	int mid = (l + r) >> 1;
	return min(get(v << 1, x, l, mid, ql, qr)
			, get(v << 1 | 1, x, mid, r, ql, qr));
}

void init(int _k, std::vector<int> r) {
	n = r.size();
	k = _k;
	for (int i = 0; i < n; i++){
		a[i] = r[i];
		add(1, 0, 0, n, i, i+1, a[i]);
		add(1, 1, 0, n, i, i+1, a[i]);
		add(1, 2, 0, n, i, i+1, inf);
	}
	vector<int> topol;
	for (int rng = 0; rng < n; rng++){
		int tmp;
		while((tmp = find0(1, 1, 0, n)) != -1){
			add(1, 0, 0, n, tmp+1, tmp+k, 1);
			if (tmp+k > n){
				add(1, 0, 0, n, 0, tmp+k-n, 1);
			}
			add(1, 1, 0, n, tmp, tmp+1, inf);
		}
		tmp = find0(1, 0, 0, n);
		add(1, 0, 0, n, tmp+1, tmp+k, -1);
		if (tmp+k > n){
			add(1, 0, 0, n, 0, tmp+k-n, -1);
		}
		add(1, 0, 0, n, tmp-k+1, tmp, -1);
		add(1, 1, 0, n, tmp-k+1, tmp, -1);
		if (tmp-k+1 < 0){
			add(1, 0, 0, n, tmp-k+1+n, n, -1);
			add(1, 1, 0, n, tmp-k+1+n, n, -1);
		}
		int mn1 = get(1, 2, 0, n, tmp+1, tmp+k);
		int mn2 = get(1, 2, 0, n, tmp-k+1, tmp);
		if (tmp+k > n){
			mn1 = min(mn1, get(1, 2, 0, n, 0, tmp+k-n));
		}
		if (tmp-k+1 < 0){
			mn2 = min(mn2, get(1, 2, 0, n, tmp-k+1+n, n));
		}
		if (mn1 != inf){
//			debug(tmp, ver[mn1]);
			par[0][tmp][0] = (ver[mn1]-tmp+n) % n;
			for (int i = 1; i < lg; i++){
				par[0][tmp][i] = par[0][tmp][i-1] + par[0][(tmp+par[0][tmp][i-1])%n][i-1];
//				debug(i, par[0][tmp][i]);
			}
		}
		if (mn2 != inf){
//			debug(tmp, ver[mn2]);
			par[1][tmp][0] = (tmp-ver[mn2]+n) % n;
			for (int i = 1; i < lg; i++){
				par[1][tmp][i] = par[1][tmp][i-1] + par[1][((tmp-par[1][tmp][i-1])%n+n)%n][i-1];
//				debug(i, par[1][tmp][i]);
			}
		}
		ver[n-rng] = tmp;
		idx[tmp] = n-rng;
		assert(tmp != -1);
		add(1, 0, 0, n, tmp, tmp+1, inf);
		add(1, 2, 0, n, tmp, tmp+1, (n-rng)-inf);
	}
}

bool ok(int x, int y){
//	debug(x, y);
	int v = x;
	int dis = (y - x + n) % n;
//	debug(v, dis);
	for (int i = lg-1; ~i; i--){
		if (par[0][v][i] <= dis){
			dis -= par[0][v][i];
			v = (v+par[0][v][i]) % n;
		}
	}
//	debug(v);
	if (v == y || (idx[y] > idx[v] && dis < k)) return true;
	v = x;
	dis = (x - y + n) % n;
//	debug(v, dis);
	for (int i = lg-1; ~i; i--){
		if (par[1][v][i] <= dis){
			dis -= par[1][v][i];
			v = (v-par[1][v][i]+n) % n;
		}
	}
	//debug(v);
	if (v == y || (idx[y] > idx[v] && dis < k)) return true;
	return false;
}

int compare_plants(int x, int y) {
	return (ok(x, y)? -1: (ok(y, x)? 1: 0));
}

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