oj.uz

Submission #317687

# Submission time Handle Problem Language Result Execution time Memory
317687 2020-10-30T07:00:21 Z arnold518 Comparing Plants (IOI20_plants) C++14
0 / 100
 161 ms 23636 KB 
#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*3+10], RR[MAXN*3+10];

int dist(int u, int v)
{
	return min(abs(u-v), N-abs(u-v));
}

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);
	for(int i=0; i<3*N; i++) LL[i]=RR[i]=i;
	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(now>p) p+=N;
			LL[now+N]=min(LL[now+N], LL[p]);
			RR[now+N]=max(RR[now+N], RR[p]);
		}
		if(t2.first!=INF)
		{
			int p=t2.second;
			if(now>p) p+=N+N;
			else p+=N;
			LL[now+N]=min(LL[now+N], LL[p]);
			RR[now+N]=max(RR[now+N], RR[p]);
		}

		LL[now]=LL[now+N]-N;
		RR[now]=RR[now+N]-N;
		LL[now+N+N]=LL[now+N]+N;
		RR[now+N+N]=RR[now+N]+N;

		LL[now]=max(LL[now], 0);
		RR[now]=min(RR[now], 3*N-1);
		seg3.update2(now, H[now]);
	}
	return;
}

bool f(int l, int r, int p)
{
	p=(p%N+N)%N;
	while(p<l) p+=N;
	return p<=r;
}

int compare_plants(int x, int y)
{
	if(f(LL[x], RR[x], y)) return -1;
	if(f(LL[y], RR[y], x)) return 1;
	return 0;
}

Compilation message

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:174: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]
  174 |  for(int i=0; i<V.size(); i++)
      |               ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19104 KB Output is correct
2 Correct 11 ms 19200 KB Output is correct
3 Correct 14 ms 19200 KB Output is correct
4 Correct 12 ms 19328 KB Output is correct
5 Correct 12 ms 19200 KB Output is correct
6 Correct 80 ms 22008 KB Output is correct
7 Incorrect 161 ms 23636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19200 KB Output is correct
2 Correct 12 ms 19200 KB Output is correct
3 Incorrect 12 ms 19328 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19200 KB Output is correct
2 Correct 12 ms 19200 KB Output is correct
3 Incorrect 12 ms 19328 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19200 KB Output is correct
2 Correct 12 ms 19200 KB Output is correct
3 Incorrect 91 ms 22264 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19200 KB Output is correct
2 Correct 12 ms 19200 KB Output is correct
3 Incorrect 12 ms 19104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19200 KB Output is correct
2 Correct 12 ms 19200 KB Output is correct
3 Incorrect 12 ms 19200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19104 KB Output is correct
2 Correct 11 ms 19200 KB Output is correct
3 Correct 14 ms 19200 KB Output is correct
4 Correct 12 ms 19328 KB Output is correct
5 Correct 12 ms 19200 KB Output is correct
6 Correct 80 ms 22008 KB Output is correct
7 Incorrect 161 ms 23636 KB Output isn't correct
8 Halted 0 ms 0 KB -