Submission #823112

#	Time	Username	Problem	Language	Result	Execution time	Memory
823112		ymm	Comparing Plants (IOI20_plants)	C++17	11 / 100	4046 ms	42056 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;
vector<int> A[N];
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;
	}
	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);
		if (l != N)
			A[pos[i]].push_back(pos[l]);
		if (r != N)
			A[pos[i]].push_back(pos[r]);
		seg1::up(pos[i], i);
	}
}

bool vis[N];
bool dfs(int v, int dst)
{
	if (v == dst)
		return 1;
	vis[v] = 1;
	for (int u : A[v]) {
		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