Submission #300887

#	Time	Username	Problem	Language	Result	Execution time	Memory
300887		ainta	Comparing Plants (IOI20_plants)	C++17	100 / 100	1061 ms	83832 KiB

plants

#include<cstdio>
#include<algorithm>
#include<cassert>
#include<set>
#define N_ 251000
#define SZ 262144
#include <vector>
using namespace std;
int n, K, Rank[N_], w[N_], V[N_];
struct Tree {
	int K[SZ + SZ], Mn[SZ + SZ];
	void UDT(int nd) {
		Mn[nd] = min(Mn[nd * 2], Mn[nd * 2 + 1]);
	}
	void init(int nd, int b, int e) {
		K[nd] = 0;
		if (b == e) {
			Mn[nd] = Rank[b] - 1;
			return;
		}
		int m = (b + e) >> 1;
		init(nd * 2, b, m);
		init(nd * 2 + 1, m + 1, e);
		UDT(nd);
	}
	void Add2(int nd, int x) {
		K[nd] += x;
		Mn[nd] += x;
	}
	void Spread(int nd) {
		Add2(nd * 2, K[nd]);
		Add2(nd * 2 + 1, K[nd]);
		K[nd] = 0;
	}
	void Add(int nd, int b, int e, int s, int l, int x) {
		if (s > l)return;
		if (s <= b && e <= l) {
			Add2(nd, x);
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		if (s <= m)Add(nd * 2, b, m, s, l, x);
		if (l > m)Add(nd * 2 + 1, m + 1, e, s, l, x);
		UDT(nd);
	}
	void Put(int nd, int b, int e, int x, int y) {
		if (b == e) {
			Mn[nd] = y;
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		if (x <= m)Put(nd * 2, b, m, x, y);
		else Put(nd * 2 + 1, m + 1, e, x, y);
		UDT(nd);
	}
	int FZ(int nd, int b, int e) {
		if (b == e)return b;
		Spread(nd);
		int m = (b + e) >> 1;
		if (!Mn[nd * 2])return FZ(nd * 2, b, m);
		return FZ(nd * 2 + 1, m + 1, e);
	}
	int FindZero() {
		if (Mn[1])return 0;
		return FZ(1, 1, n);
	}
}IT;
set<int>Set, Good;
void Ins(int a) {
	Set.insert(a);
	auto it = Set.find(a);
	int nxt, prv;
	if (next(it) != Set.end())nxt = *(next(it));
	else nxt = (*Set.begin()) + n;
	if (it != Set.begin())prv = *(prev(it));
	else prv = (*prev(Set.end())) - n;
	if (nxt - a >= K) {
		int t = (nxt - 1) % n + 1;
		Good.insert(t);
	}
	else {
		int t = (nxt - 1) % n + 1;
		if (Good.find(t) != Good.end()) Good.erase(t);
	}
	if (a - prv >= K) {
		Good.insert(a);
	}
}
void Del(int a) {
	auto it = Set.find(a);
	int nxt, prv;
	if (next(it) != Set.end())nxt = *(next(it));
	else nxt = (*Set.begin()) + n;
	if (it != Set.begin())prv = *(prev(it));
	else prv = (*prev(Set.end())) - n;
	Set.erase(a);
 
	if (Good.find(a) != Good.end())Good.erase(a);
 
	if (!Set.empty() && nxt - prv >= K) {
		Good.insert((nxt - 1) % n + 1);
	}
}
 
 
int BIT[N_];
void Add(int a, int b) {
	while (a < N_) {
		BIT[a] += b;
		a += (a&-a);
	}
}
int Sum(int a) {
	int r = 0;
	while (a) {
		r += BIT[a];
		a -= (a&-a);
	}
	return r;
}
 
long long Right[N_][20], Left[N_][20], INF = 1e9;
 
bool RightPath(int a, int b) {
	int d = (b - a + n) % n;
	int i;
	for (i = 17; i >= 0; i--) {
		if (d >= Right[a][i]) {
			d -= Right[a][i];
			a = (a + Right[a][i] - 1) % n + 1;
		}
	}
	if ((b - a + n) % n < K && V[a] <= V[b])return true;
	return false;
}
 
 
bool LeftPath(int a, int b) {
	int d = (a - b + n) % n;
	int i;
	for (i = 17; i >= 0; i--) {
		if (d >= Left[a][i]) {
			d -= Left[a][i];
			a = (a - Left[a][i] - 1 + n) % n + 1;
		}
	}
	if ((a - b + n) % n < K && V[a] <= V[b])return true;
	return false;
}
 
bool Path(int a, int b) {
	return RightPath(a, b) || LeftPath(a, b);
}
 
int compare_plants(int a, int b) {
	a++;
	b++;
	if (Path(a, b)) return 1;
	else if (Path(b, a)) return -1;
	else return 0;
}
 
void Do() {
	int i, j;
	for (i = 0; i < N_; i++)BIT[i] = 0;
	for (i = 1; i <= K; i++) {
		Add(V[i], 1);
	}
 
	for (i = 1; i <= n; i++) {
 
		int b = V[i] + 1, e = n, mid, r = 0, s = Sum(V[i]);
		while (b <= e) {
			mid = (b + e) >> 1;
			if (Sum(mid) > s) {
				r = mid;
				e = mid - 1;
			}
			else b = mid + 1;
		}
		if (r) {
			r = w[r];
			Right[i][0] = (r - i + n) % n;
		}
		else Right[i][0] = INF;
 
		Add(V[i], -1);
		Add(V[(i + K - 1) % n + 1], 1);
	}
 
	for (i = 0; i < N_; i++)BIT[i] = 0;
 
	for (i = n; i > n - K; i--) {
		Add(V[i], 1);
	}
	for (i = n; i >= 1; i--) {
 
 
		int b = V[i] + 1, e = n, mid, r = 0, s = Sum(V[i]);
		while (b <= e) {
			mid = (b + e) >> 1;
			if (Sum(mid) > s) {
				r = mid;
				e = mid - 1;
			}
			else b = mid + 1;
		}
		if (r) {
			r = w[r];
			Left[i][0] = (i - r + n) % n;
		}
		else Left[i][0] = INF;
 
		Add(V[i], -1);
		Add(V[(i - K + n - 1) % n + 1], 1);
	}
	for (i = 0; i < 18; i++) {
		for (j = 1; j <= n; j++) {
			if (Right[j][i] >= INF) {
				Right[j][i + 1] = INF;
			}
			else {
				int t = (j + Right[j][i] - 1) % n + 1;
				Right[j][i + 1] = min(INF, Right[t][i] + Right[j][i]);
			}
			if (Left[j][i] >= INF) {
				Left[j][i + 1] = INF;
			}
			else {
				int t = (j - Left[j][i] % n - 1 + n) % n + 1;
				Left[j][i + 1] = min(INF, Left[t][i] + Left[j][i]);
			}
		}
	}
}
 
void init(int k, vector<int> r) {
	n = r.size();
	K = k;
	int i;
	for(i=0; i<n; i++) {
		Rank[i+1] = r[i]+1;
	}
	IT.init(1, 1, n);
	for (i = 1; i <= n; i++) {
 
		int t;
		while ((t = IT.FindZero())) {
			Ins(t);
			IT.Put(1, 1, n, t, INF);
		}
		assert(!Good.empty());
		int a = *Good.begin();
		w[i] = a;
		V[a] = i;
		IT.Add(1, 1, n, max(a - K + 1, 1), a - 1, -1);
		IT.Add(1, 1, n, a - K + 1 + n, min(a - 1 + n, n), -1);
		Del(a);
	}
	for (i = 1; i <= K; i++) Add(V[i], 1);
	for (i = 1; i <= n; i++) {
		assert(Sum(V[i]) == Rank[i]);
		Add(V[i], -1);
		Add(V[(i + K - 1) % n + 1], 1);
	}
	Do();
}

• 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