Submission #823164

#	Time	Username	Problem	Language	Result	Execution time	Memory
823164		ymm	Comparing Plants (IOI20_plants)	C++17	11 / 100	4090 ms	91628 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= l; --x)
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 200'010;
const int lg = 20;
ll L[N][lg], R[N][lg];
int val[N], pos[N];
int n, k;

namespace seg1 {
	int a[2*N];
	void init() { fill(a, a+2*N, N); }

	void up(int p, int x) {
		p += N;
		while (p > 0) {
			a[p] = x;
			p /= 2;
		}
	}
	int get(int l, int r) {
		l += N;
		r += N;
		int ans = N;
		while (l < r) {
			if (l&1) ans = min(ans, a[l++]);
			if (r&1) ans = min(ans, a[--r]);
			l /= 2;
			r /= 2;
		}
		return ans;
	}
	int getc(int l, int r) {
		--r;
		l = (l%n+n)%n;
		r = (r%n+n)%n;
		++r;
		if (l >= r)
			return min(get(0, r), get(l, n));
		else
			return get(l, r);
	}
}

namespace seg2 {
	struct node {
		int mn;
		int lzy;
		int l, r;
		pii mxdif;
	} t[N*4];
	int sz;

	void merge(int i) {
		node &v = t[i], &l = t[2*i+1], &r = t[2*i+2];
		if (l.mn == r.mn) {
			v.mn = l.mn;
			v.l = l.l;
			v.r = r.r;
			v.mxdif = max(l.mxdif, r.mxdif);
			v.mxdif = max(v.mxdif, pii{r.l - l.r, r.l});
		} else {
			node &u = l.mn < r.mn? l: r;
			v = u;
			v.lzy = 0;
		}
	}
	void tag(int i, int x) { t[i].mn += x; t[i].lzy += x; }
	void ppg(int i) {
		if (t[i].lzy) {
			tag(2*i+1, t[i].lzy);
			tag(2*i+2, t[i].lzy);
			t[i].lzy = 0;
		}
	}

	void init(const vector<int> &vec, int i, int b, int e) {
		if (e-b == 1) {
			t[i].mn = vec[b];
			t[i].l = t[i].r = b;
			t[i].mxdif = {-1, -1};
			return;
		}
		init(vec, 2*i+1, b, (b+e)/2);
		init(vec, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void init(const vector<int> &vec) { sz = vec.size(); init(vec, 0, 0, sz); }

	void add(int l, int r, int x, int i, int b, int e) {
		if (l <= b && e <= r)
			return tag(i, x);
		if (r <= b || e <= l)
			return;
		ppg(i);
		add(l, r, x, 2*i+1, b, (b+e)/2);
		add(l, r, x, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void add(int l, int r, int x) { add(l, r, x, 0, 0, sz); }
	void addc(int l, int r, int x) {
		--r;
		l = (l%n+n)%n;
		r = (r%n+n)%n;
		++r;
		if (l >= r) {
			add(0, r, x);
			add(l, sz, x);
		} else {
			add(l, r, x);
		}
	}

	int get() {
		if (t[0].mxdif.first >= k)
			return t[0].mxdif.second;
		else
			return t[0].l;
	}
}

void init(int k, std::vector<int> r) {
	::k = k;
	n = r.size();
	seg2::init(r);
	LoopR (x,0,n) {
		int p = seg2::get();
		seg2::addc(p-k+1, p, -1);
		seg2::add(p, p+1, N);
		val[p] = x;
		pos[x] = p;
		//cerr << p << "-\n";
	}
	seg1::init();
	LoopR (i,0,n) {
		int l = seg1::getc(pos[i]-k+1, pos[i]);
		int r = seg1::getc(pos[i]+1, pos[i]+k);
		seg1::up(pos[i], i);
		L[pos[i]][0] = l == N? 0: (pos[i]-pos[l]+n)%n;
		R[pos[i]][0] = r == N? 0: (pos[r]-pos[i]+n)%n;
	}
	Loop (j,0,lg-1) {
		Loop (i,0,n) {
			int l = ((i - L[i][j])%n+n)%n;
			int r = ((i + R[i][j])%n+n)%n;
			L[i][j+1] = L[i][j] + L[l][j];
			R[i][j+1] = R[i][j] + R[r][j];
		}
	}
	//Loop (i,0,n)
	//	cerr << L[i][0] << ' ';
	//cerr << '\n';
	//Loop (i,0,n)
	//	cerr << R[i][0] << ' ';
	//cerr << '\n';
}

bool try_left(int x, int y)
{
	ll dis = 0;
	while (L[x][0]) {
		int x2 = ((x - L[x][0])%n+n)%n;
		if (val[x2] > val[y])
			break;
		dis += L[x][0];
		x = x2;
	}
	//LoopR (i,0,lg) {
	//	int x2 = ((x - L[x][i])%n+n)%n;
	//	if (val[x2] <= val[y]) {
	//		dis += L[x][i];
	//		x = x2;
	//	}
	//}
	return (x-y+n)%n <= dis;
}
bool try_right(int x, int y)
{
	ll dis = 0;
	while (R[x][0]) {
		int x2 = ((x + R[x][0])%n+n)%n;
		if (val[x2] > val[y])
			break;
		dis += R[x][0];
		x = x2;
	}
	//LoopR (i,0,lg) {
	//	int x2 = ((x + R[x][i])%n+n)%n;
	//	if (val[x2] <= val[y]) {
	//		dis += R[x][i];
	//		x = x2;
	//	}
	//}
	return (y-x+n)%n <= dis;
}
bool try_lr(int x, int y) { return try_left(x, y) || try_right(x, y); }

//int compare_plants(int x, int y) {
//	if (val[x] < val[y]) {
//		if (try_lr(x, y))
//			return -1;
//		else
//			return 0;
//	} else {
//		if (try_lr(y, x))
//			return 1;
//		else
//			return 0;
//	}
//}

bool vis[N];
bool dfs(int v, int dst)
{
	if (v == dst)
		return 1;
	vis[v] = 1;
	int l = ((v - L[v][0])%n+n)%n;
	int r = ((v + R[v][0])%n+n)%n;
	for (int u : {l, r}) {
		if (!vis[u] && dfs(u, dst))
			return 1;
	}
	return 0;
}

int compare_plants(int x, int y) {
	//if (val[x] > val[y])
	//	return 1;
	//else
	//	return -1;
	memset(vis, 0, n);
	if (dfs(x, y))
		return -1;
	memset(vis, 0, n);
	if (dfs(y, x))
		return 1;
	return 0;
}

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