Submission #318237

#	Time	Username	Problem	Language	Result	Execution time	Memory
318237		arnold518	Comparing Plants (IOI20_plants)	C++14	100 / 100	2262 ms	130264 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int INF = 1e8;

int N, K, R[MAXN+10], H[MAXN+10];

struct SEG
{
	pii tree[MAXN*4+10];
	int lazy[MAXN*4+10];

	void busy(int node, int tl, int tr)
	{
		tree[node].first+=lazy[node];
		if(tl!=tr)
		{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	void init(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			tree[node]={0, tl};
			lazy[node]=0;
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}
	void update(int node, int tl, int tr, int l, int r, int k)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r)
		{
			lazy[node]+=k;
			busy(node, tl, tr);
			return;
		}
		if(r<tl || tr<l) return;
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}
	void update2(int node, int tl, int tr, int p, int k)
	{
		busy(node, tl, tr);
		if(tl==tr)
		{
			tree[node].first=k;
			return;
		}
		int mid=tl+tr>>1;
		if(p<=mid) update2(node*2, tl, mid, p, k);
		else update2(node*2+1, mid+1, tr, p, k);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}
	pii query(int node, int tl, int tr, int l, int r)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r) return tree[node];
		if(r<tl || tr<l) return {INF, -1};
		int mid=tl+tr>>1;
		return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
	}
	void query2(int node, int tl, int tr, int l, int r, vector<int> &V)
	{
		busy(node, tl, tr);
		if(tree[node].first!=0) return;
		if(r<tl || tr<l) return;
		if(tl==tr)
		{
			V.push_back(tl);
			return;
		}
		int mid=tl+tr>>1;
		query2(node*2, tl, mid, l, r, V);
		query2(node*2+1, mid+1, tr, l, r, V);
	}
	void init()
	{
		init(1, 0, N-1);
	}
	void update(int l, int r, int k)
	{
		l=(l%N+N)%N; r=(r%N+N)%N;
		if(l<=r) update(1, 0, N-1, l, r, k);
		else
		{
			update(1, 0, N-1, l, N-1, k);
			update(1, 0, N-1, 0, r, k);
		}
	}
	void update2(int p, int k)
	{
		p=(p%N+N)%N;
		update2(1, 0, N-1, p, k);
	}
	pii query(int l, int r)
	{
		l=(l%N+N)%N; r=(r%N+N)%N;
		if(l<=r) return query(1, 0, N-1, l, r);
		else return min(query(1, 0, N-1, l, N-1), query(1, 0, N-1, 0, r));
	}
	vector<int> query2(int l, int r)
	{
		vector<int> ret;
		l=(l%N+N)%N; r=(r%N+N)%N;
		if(l<=r) query2(1, 0, N-1, l, r, ret);
		else
		{
			query2(1, 0, N-1, l, N-1, ret);
			query2(1, 0, N-1, 0, r, ret);
		}
		return ret;
	}
}seg1, seg2, seg3;

int LL[MAXN*2+10][30], RR[MAXN*2+10][30];

void init(int _K, vector<int> _R)
{
	K=_K; N=_R.size();
	for(int i=0; i<N; i++) R[i]=_R[i];
	seg1.init(); seg2.init(); seg3.init();

	for(int i=0; i<N; i++)
	{
		seg1.update2(i, R[i]);
		seg2.update2(i, R[i]);
	}
	for(int i=0; i<N; i++) if(R[i]==0) seg1.update(i+1, i+K-1, 1);

	for(int i=N-1; i>=0; i--)
	{
		vector<int> V;
		assert(seg1.tree[1].first+seg1.lazy[1]==0);
		int now=seg1.tree[1].second; H[now]=i;
		assert(seg2.query(now-K+1, now-1).first>=1);
		seg1.update(now+1, now+K-1, -1);
		seg1.update2(now, INF);
		seg2.update2(now, INF);
		seg2.update(now-K+1, now-1, -1);
		seg1.update(now-K+1, now-1, -1);

		V=seg2.query2(now-K+1, now-1);
		for(auto it : V) seg1.update(it+1, it+K-1, 1);
	}
	//for(int i=0; i<N; i++) printf("%d ", H[i]); printf("\n");
	
	vector<pii> V;
	for(int i=0; i<N; i++) V.push_back({H[i], i});
	sort(V.begin(), V.end(), greater<pii>());
	
	for(int i=0; i<N; i++) seg3.update2(i, INF);

	memset(LL, -1, sizeof(LL));
	memset(RR, -1, sizeof(RR));
	for(int i=0; i<V.size(); i++)
	{
		int now=V[i].second;
		pii t1=seg3.query(now-K+1, now), t2=seg3.query(now, now+K-1);

		if(t1.first!=INF)
		{
			int p=t1.second;
			if(p<now)
			{
				LL[now][0]=p;
				LL[now+N][0]=p+N;
			}
			else
			{
				LL[now+N][0]=p;
			}
		}
		if(t2.first!=INF)
		{
			int p=t2.second;
			if(now<p)
			{
				RR[now][0]=p;
				RR[now+N][0]=p+N;
			}
			else
			{
				RR[now][0]=p+N;
			}
		}
		seg3.update2(now, H[now]);
	}
 	
	for(int i=1; i<=20; i++)
	{
		for(int j=0; j<N+N; j++)
		{
			if(LL[j][i-1]!=-1) LL[j][i]=LL[LL[j][i-1]][i-1];
			if(RR[j][i-1]!=-1) RR[j][i]=RR[RR[j][i-1]][i-1];	
		}
	}

	//for(int i=0; i<N+N; i++) printf("%d %d : %d %d\n", i, H[i%N], LL[i][0], RR[i][0]);

	return;
}

int compare_plants(int x, int y)
{
	int ans=0;

	//printf("%d %d : %d %d\n", x, y, H[x], H[y]);
	if(x<y)
	{
		if(H[x]<H[y])
		{
			int now=x+N;
			for(int i=20; i>=0; i--)
			{
				if(RR[now][i]!=-1 && RR[now][i]<y+N) now=RR[now][i];
			}
			if(now+K-1>=y+N && H[now%N]<=H[y]) return -1;

			now=x+N;
			for(int i=20; i>=0; i--)
			{
				if(LL[now][i]!=-1 && LL[now][i]>y) now=LL[now][i];
			}
			if(now-K+1<=y && H[now%N]<=H[y]) return -1;
		}
		else
		{
			int now=y;
			for(int i=20; i>=0; i--)
			{
				if(RR[now][i]!=-1 && RR[now][i]<x+N) now=RR[now][i];
			}
			if(now+K-1>=x+N && H[now%N]<=H[x]) return 1;
			
			now=y;
			for(int i=20; i>=0; i--)
			{
				if(LL[now][i]!=-1 && LL[now][i]>x) now=LL[now][i];
			}
			if(now-K+1<=x && H[now%N]<=H[x]) return 1;
		}
	}
	else
	{
		if(H[x]<H[y])
		{
			int now=x;
			for(int i=20; i>=0; i--)
			{
				if(RR[now][i]!=-1 && RR[now][i]<y+N) now=RR[now][i];
			}
			if(now+K-1>=y+N && H[now%N]<=H[y]) return -1;

			now=x;
			for(int i=20; i>=0; i--)
			{
				if(LL[now][i]!=-1 && LL[now][i]>y) now=LL[now][i];
			}
			if(now-K+1<=y && H[now%N]<=H[y]) return -1;
		}
		else
		{
			int now=y+N;
			for(int i=20; i>=0; i--)
			{
				if(RR[now][i]!=-1 && RR[now][i]<x+N) now=RR[now][i];
			}
			if(now+K-1>=x+N && H[now%N]<=H[x]) return 1;
			
			now=y+N;
			for(int i=20; i>=0; i--)
			{
				if(LL[now][i]!=-1 && LL[now][i]>x) now=LL[now][i];
			}
			if(now-K+1<=x && H[now%N]<=H[x]) return 1;
		}
	}
	return 0;
}

Compilation message (stderr)

plants.cpp: In member function 'void SEG::init(int, int, int)':
plants.cpp:37:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
plants.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'void SEG::update2(int, int, int, int, int)':
plants.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'pii SEG::query(int, int, int, int, int)':
plants.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'void SEG::query2(int, int, int, int, int, std::vector<int>&)':
plants.cpp:88:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:171:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |  for(int i=0; i<V.size(); i++)
      |               ~^~~~~~~~~
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:221:6: warning: unused variable 'ans' [-Wunused-variable]
  221 |  int ans=0;
      |      ^~~

• 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