제출 #468016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
468016		blue	식물 비교 (IOI20_plants)	C++17	32 / 100	3815 ms	122020 KiB

plants

#include "plants.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int N;
int K;

const long long INF = 1e9;

struct segtree
{
	int l;
	int r;

	pair<long long, int> mn; //min first, index second
	pair<long long, int> mx; //max first, index second
	int lp = 0;

	segtree* left = NULL;
	segtree* right = NULL;

	segtree()
	{
		;
	}

	segtree(int L, int R)
	{
		l = L;
		r = R;

		mn = make_pair(0, l);
		mx = make_pair(0, l);

		if(l == r) return;

		int m = (l+r)/2;

		left = new segtree(l, m);
		right = new segtree(m+1, r);
	}

	void add(int L, int R, long long V)
	{
		L = (L + 10*N) % N;
		R = (R + 10*N) % N;


		if(R < L)
		{
			add(L, N-1, V);
			add(0, R, V);
			return;
		}

		if(R < l || r < L) return;
		else if(L <= l && r <= R)
		{
			lp += V;
			mn.first += V;
			mx.first += V;
		}
		else
		{
			left->add(L, R, V);
			right->add(L, R, V);

			mn = min(left->mn, right->mn);
			mn.first += lp;

			mx = max(left->mx, right->mx);
			mx.first += lp;
		}
	}

	pair<long long, int> rangemin(int L, int R)
	{
		L = (L + 10*N) % N;
		R = (R + 10*N) % N;

		if(R < L)
		{
			return min(rangemin(L, N-1), rangemin(0, R));
		}

		if(R < l || r < L) return make_pair(+2*INF, -1);
		else if(L <= l && r <= R)
		{
			return mn;
		}
		else
		{
			pair<long long, int> A = min(left->rangemin(L, R), right->rangemin(L, R));
			A.first += lp;
			return A;
		}
	}

	pair<long long, int> rangemax(int L, int R)
	{
		L = (L + 10*N) % N;
		R = (R + 10*N) % N;

		if(R < L)
		{
			return max(rangemax(L, N-1), rangemax(0, R));
		}

		if(R < l || r < L) return make_pair(-2*INF, -1);
		else if(L <= l && r <= R)
		{
			return mx;
		}
		else
		{
			pair<long long, int> A = max(left->rangemax(L, R), right->rangemax(L, R));
			A.first += lp;
			// cerr << "returning " << A.first << ' ' << A.second << " for rangemax " << L << ' ' << R << '\n';
			return A;
		}
	}
};

segtree R;
vector<int> pos;

int dist(int x, int y) //clockwise distance from x to y
{
	x = x % N;
	y = y % N;
	if(y < x) y += N;
	return y-x;
}

const int maxN = 200'000;
const int lgN = 18;

int right_high[maxN][lgN];
int left_high[maxN][lgN];
int right_low[maxN][lgN];
int left_low[maxN][lgN];

vector<int> H;

void init(int k, vector<int> r)
{
	N = r.size();
	K = k;


	segtree R(0, N-1);

	segtree S(0, N-1);

	for(int i = 0; i < N; i++)
	{
		R.add(i, i, +r[i]);

		if(r[i] >= 1)
			S.add(i+1, i+K-1, +1);

		if(r[i] != 0)
			S.add(i, i, -INF);
	}



	vector<int> inv_h_order;

	for(int t = 0; t < N; t++)
	{
		pair<long long, int> p = S.rangemax(0, N-1);
		int I = p.second;
		inv_h_order.push_back(I);
		// cerr << "I = " << I << '\n';

		R.add(I, I, +INF);
		S.add(I, I, -INF);
		S.add(I+1, I+K-1, +1);


		vector<int> newzeros;
		// R.add(I+1, I+K-1, -1);
		R.add(I-K+1, I-1, -1);
		while(1)
		{
			// for(int i = 0; i < N; i++) cerr << R.rangemin(i, i).second << ' ';
			// cerr << '\n';


			pair<long long, int> q = R.rangemin(I-K+1, I-1);
			if(q.first > 0) break;
			// cerr << "q = " << q.second << '\n';
			newzeros.push_back(q.second);
			R.add(q.second, q.second, +1);
		}
		for(int z: newzeros)
		{
			R.add(z, z, -1);
			S.add(z, z, +INF);
		}

		for(int z: newzeros)
			S.add(z+1, z+K-1, -1);
	}

	vector<int> h(N);
	for(int i = 0; i < N; i++) h[ inv_h_order[i] ] = N-1 - i;





	pos = vector<int>(N);
	for(int i = 0; i < N; i++)
		pos[ h[i] ] = i;



	set<int> highpos;

	left_high[ pos[N-1] ][0] = pos[N-1];
	right_high[ pos[N-1] ][0] = pos[N-1];
	highpos.insert(pos[N-1]);
	highpos.insert(pos[N-1] + N);
	for(int u = N-2; u >= 0; u--)
	{
		// cerr << "u = " << u << '\n';
		set<int>::iterator rh = highpos.upper_bound(pos[u]);
		if(dist(pos[u], *rh) >= K)
			right_high[ pos[u] ][0] = pos[u];
		else
			right_high[ pos[u] ][0] = (*rh) % N;

		// cerr << "part 2\n";

		set<int>::iterator lh = highpos.upper_bound(pos[u] + N);
		lh--;
		if(dist(*lh, pos[u]) >= K)
			left_high[ pos[u] ][0] = pos[u];
		else
			left_high[ pos[u] ][0] = (*lh) % N;

		highpos.insert(pos[u]);
		highpos.insert(pos[u] + N);
	}
	// cerr << "done\n";

	// for(int i = 0; i < N; i++) cerr << left_high[i][0] << ' ' << right_high[i][0] << '\n';



	for(int e = 1; e < lgN; e++)
	{
		for(int i = 0; i < N; i++)
		{
			right_high[i][e] = right_high[ right_high[i][e-1] ][e-1];
			left_high[i][e] = left_high[ left_high[i][e-1] ][e-1];
		}
	}

	H = h;
	for(int i = 0; i < N; i++) cerr << H[i] << ' ';
	cerr << '\n';
}

bool query_right(int x, int y)
{
	if(dist(x, y) < K || dist(y, x) < K)
	{
		return H[x] < H[y];
	}

	for(int e = lgN - 1; e >= 0; e--)
	{
		if(H[ right_high[x][e] ] > H[y]) continue;
		else if(H[ right_high[x][e] ] == H[y]) return 1;

		if(dist(x, right_high[x][e]) + dist(right_high[x][e], y) > dist(x, y))
			continue;

		x = right_high[x][e];
	}

	if(dist(x, y) < K || dist(y, x) < K)
	{
		return H[x] < H[y];
	}

	return 0;
}

bool query_left(int x, int y)
{
	if(dist(x, y) < K || dist(y, x) < K)
	{
		return H[x] < H[y];
	}

	for(int e = lgN - 1; e >= 0; e--)
	{
		if(H[ left_high[x][e] ] > H[y]) continue;
		else if(H[ left_high[x][e] ] == H[y]) return 1;

		if(dist(left_high[x][e], x) + dist(y, left_high[x][e]) > dist(y, x))
			continue;

		x = left_high[x][e];
	}

	if(dist(x, y) < K || dist(y, x) < K)
	{
		return H[x] < H[y];
	}

	return 0;
}

int compare_plants(int x, int y)
{
	if(query_left(x, y)) return -1;
	if(query_right(x, y)) return -1;
	if(query_left(y, x)) return 1;
	if(query_right(y, x)) return 1;
	return 0;
}

• 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