제출 #301126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
301126		justtestingthis2	식물 비교 (IOI20_plants)	C++14	27 / 100	1055 ms	25856 KiB

plants

#include<bits/stdc++.h>
#include "plants.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 200005;
const int MXS = N * 4;
int n, k, A[N], P[2][N], rev[2][N];
int wset;
struct CMP {
	inline int operator() (int a, int b) const {
		if (!wset)
			return a < b;
		return rev[0][a] > rev[0][b];
	};
};
queue < int > Todo;
vector < int > res;
struct SEGT
{
	int MN[MXS], LZ[MXS];
	int le, ri, val;
	inline void Reset()
	{
		memset(MN, 0, sizeof(MN));
		memset(LZ, 0, sizeof(LZ));
	}
	inline void Shift(int id)
	{
		MN[lc] += LZ[id];
		MN[rc] += LZ[id];
		LZ[lc] += LZ[id];
		LZ[rc] += LZ[id];
		LZ[id] = 0;
		return ;
	}
	void Adder(int id = 1, int l = 0, int r = n)
	{
		if (ri <= l || r <= le)
			return ;
		if (le <= l && r <= ri)
		{
			MN[id] += val;
			LZ[id] += val;
			return ;
		}
		Shift(id);
		Adder(lc, l, md);
		Adder(rc, md, r);
		MN[id] = min(MN[lc], MN[rc]);
	}
	inline void Add(int l, int r, int vl)
	{
		val = vl;

		if (l < 0)
			l += n, r += n;
		assert(r - n <= l);
		assert(l >= 0);

		if (r <= n)
		{
			le = l; ri = r;
			Adder();
		}
		else
		{
			le = l; ri = n;
			Adder();
			le = 0; ri = r - n;
			Adder();
		}
	}
	void Extract(int id = 1, int l = 0, int r = n)
	{
		assert(MN[id] >= 0);
		if (MN[id] > 0)
			return ;
		if (r - l < 2)
			return void(res.push_back(l));
		Shift(id);
		Extract(lc, l, md);
		Extract(rc, md, r);
	}
};
pair < int , int > F[N];
SEGT SG[2];
/*bitset < N > Ad[N];
int Mark[N];
void DFS(int v)
{
	Mark[v] = 1;
	for (int u = 0; u < n; u ++)
		if (Ad[v][u])
		{
			if (!Mark[u])
				DFS(u);
			Ad[v] |= Ad[u];
		}
}*/
int MN[N * 4], MX[N * 4];
int segn;
inline void Do(int i, int av, int bv)
{
	i += segn;
	if (av < 0)
		av += n, bv += n;
	MN[i] = av;
	MX[i] = bv;
	for (; i; i >>= 1)
	{
		MN[i >> 1] = min(MN[i], MN[i ^ 1]);
		MX[i >> 1] = max(MX[i], MX[i ^ 1]);
	}
}
inline pair < int , int > Get(int l, int r)
{
	pair < int , int > ret = {l, r};
	for (l += segn, r += segn; l < r; l >>= 1, r >>= 1)
	{
		if (l & 1)
		{
			ret.first = min(ret.first, MN[l]);
			ret.second = max(ret.second, MX[l]);
			l ++;
		}
		if (r & 1)
		{
			r --;
			ret.first = min(ret.first, MN[r]);
			ret.second = max(ret.second, MX[r]);
		}
	}
	if (ret.first < 0)
		ret.first += n, ret.second += n;
	if (ret.second >= ret.first + n)
		ret = {0, n};
	return ret;
}
inline pair < int , int > Query(int le, int ri)
{
	int mn = le;
	int mx = ri;
	assert(le >= 0 && ri <= n + n);
	assert(le >= 0);
	pair < int , int > ret = Get(le, ri);
	mn = min(mn, ret.first);
	mx = max(mx, ret.second);
	ret = Get(max(le - n, 0), max(ri - n, 0));
	mn = min(mn, ret.first);
	mx = max(mx, ret.second);
	ret = Get(min(le + n, segn), min(ri + n, segn));
	mn = min(mn, ret.first);
	mx = max(mx, ret.second);
	if (mn < 0)
		mn += n, mx += n;
	if (mn >= n)
		mn -= n, mx -= n;
	mx = min(mx, n + n);
	return make_pair(mn, mx);
}

void init(int _k, vector < int > _r)
{
	k = _k;
	n = (int)_r.size();
	for (int i = 0; i < n; i ++)
		A[i] = _r[i];

	for (int w = 0; w <= 0; w ++)
	{
		wset = w;
		SG[0].Reset();
		SG[1].Reset();
		for (int i = 0; i < n; i ++)
		{
			if (A[i])
			{
				SG[1].Add(i, i + 1, 1);
				SG[0].Add(i, i + 1, A[i]);
			}
			else
			{
				SG[1].Add(i + 1, i + k, 1);
				SG[0].Add(i, i + 1, N);
			}
		}

		vector < int > M(n, 0);
		for (int __ = 0; __ < n; __ ++)
		{
			res.clear();
			SG[1].Extract();
			for (int i : res)
				Todo.push(i);
			res.clear();
			assert((int)Todo.size());
			int i = Todo.front();
			M[i] = 1;
          Todo.pop();

			/*for (int j = i - k + 1; j < i + k; j ++)
			{
				int tt = j;
				if (tt < 0) tt += n;
				if (tt >= n) tt -= n;
				if (M[tt])
					continue;
				Ad[tt][i] = 1;
			}*/
			F[i] = {i - k + 1, i + k};


			P[w][__] = i;
			rev[w][i] = __;

			SG[1].Add(i, i + 1, N);
			SG[0].Add(i - k + 1, i, -1);
			SG[1].Add(i + 1, i + k, -1);

			res.clear();
			SG[0].Extract();
			for (int j : res)
			{
				SG[1].Add(j, j + 1, -1);
				SG[1].Add(j + 1, j + k, 1);
				SG[0].Add(j, j + 1, N);

			}
			res.clear();
		}

		/*for (int i = 0; i < n; i ++)
		  printf("%d ", P[w][i]);
		 printf("\n");*/
	}
	/*for (int i = 0; i < n; i ++)
		if (!Mark[i])
			DFS(i);*/

/*	segn = n + n;

	memset(MN, 63, sizeof(MN));
	memset(MX, -63, sizeof(MX));
	for (int h = n - 1; h >= 0; h --)
	{
		int i = P[0][h];

//		printf("=== %d :: %d , %d\n", i, F[i].first, F[i].second);
		if (F[i].first < 0)
			F[i].first += n, F[i].second += n;
		if (F[i].first >= n)
			F[i].first -= n, F[i].second -= n;
		F[i].second = min(F[i].second, segn);

		F[i] = Query(F[i].first, F[i].second);
		if (F[i].first < 0)
			F[i].first += n, F[i].second += n;
		if (F[i].first >= n)
			F[i].first -= n, F[i].second -= n;
		F[i].second = min(F[i].second, segn);
		Do(i, F[i].first, F[i].second);
		Do(i + n, F[i].first, F[i].second);

//		printf("%d :: %d , %d\n", i, F[i].first, F[i].second);
	}*/
	return ;

/*	for (int i = 0; i < n; i ++)
	{
		printf("%d :: %d\n", F[i].first, F[i].second);
	}*/
}
inline bool Check(pair < int , int > ff, int i)
{
	int l = ff.first;
	int r = ff.second;

	if (l < 0)
		l += n, r += n;
	if (l <= i && i < r)
		return 1;
	if (l <= i + n && i + n < r)
		return 1;
	return 0;
}

int compare_plants(int a, int b)
{
	if (rev[0][a] < rev[0][b])
		return 1;
	return -1;
	/*if (Ad[a][b])
		return -1;
	if (Ad[b][a])
		return 1;
	return 0;*/
	if (rev[0][a] < rev[0][b] && Check(F[a], b))
		return 1;
	if (rev[0][b] < rev[0][a] && Check(F[b], a))
		return -1;
	return 0;
}

• Subtask 1: 0 / 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