oj.uz

Submission #318241

# Submission time Handle Problem Language Result Execution time Memory
318241 2020-10-31T16:25:10 Z arnold518 Comparing Plants (IOI20_plants) C++14
100 / 100
 2277 ms 127316 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*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];	
		}
	}

	return;
}

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

	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

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:219:6: warning: unused variable 'ans' [-Wunused-variable]
  219 |  int ans=0;
      |      ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 113124 KB Output is correct
2 Correct 61 ms 113124 KB Output is correct
3 Correct 61 ms 113276 KB Output is correct
4 Correct 60 ms 113124 KB Output is correct
5 Correct 60 ms 113124 KB Output is correct
6 Correct 148 ms 116716 KB Output is correct
7 Correct 257 ms 117820 KB Output is correct
8 Correct 1126 ms 127124 KB Output is correct
9 Correct 1145 ms 127144 KB Output is correct
10 Correct 1176 ms 127316 KB Output is correct
11 Correct 1205 ms 127316 KB Output is correct
12 Correct 1226 ms 127188 KB Output is correct
13 Correct 1248 ms 127316 KB Output is correct
14 Correct 1227 ms 127312 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 113124 KB Output is correct
2 Correct 62 ms 113124 KB Output is correct
3 Correct 59 ms 113124 KB Output is correct
4 Correct 59 ms 113124 KB Output is correct
5 Correct 59 ms 113124 KB Output is correct
6 Correct 67 ms 113252 KB Output is correct
7 Correct 161 ms 116704 KB Output is correct
8 Correct 61 ms 113124 KB Output is correct
9 Correct 68 ms 113252 KB Output is correct
10 Correct 163 ms 116796 KB Output is correct
11 Correct 179 ms 116576 KB Output is correct
12 Correct 165 ms 116832 KB Output is correct
13 Correct 162 ms 116660 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 113124 KB Output is correct
2 Correct 62 ms 113124 KB Output is correct
3 Correct 59 ms 113124 KB Output is correct
4 Correct 59 ms 113124 KB Output is correct
5 Correct 59 ms 113124 KB Output is correct
6 Correct 67 ms 113252 KB Output is correct
7 Correct 161 ms 116704 KB Output is correct
8 Correct 61 ms 113124 KB Output is correct
9 Correct 68 ms 113252 KB Output is correct
10 Correct 163 ms 116796 KB Output is correct
11 Correct 179 ms 116576 KB Output is correct
12 Correct 165 ms 116832 KB Output is correct
13 Correct 162 ms 116660 KB Output is correct
14 Correct 279 ms 117568 KB Output is correct
15 Correct 2239 ms 126936 KB Output is correct
16 Correct 277 ms 117608 KB Output is correct
17 Correct 2229 ms 127188 KB Output is correct
18 Correct 1670 ms 126936 KB Output is correct
19 Correct 1656 ms 126856 KB Output is correct
20 Correct 2013 ms 126868 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 113124 KB Output is correct
2 Correct 62 ms 113124 KB Output is correct
3 Correct 158 ms 116836 KB Output is correct
4 Correct 1411 ms 126932 KB Output is correct
5 Correct 1596 ms 126756 KB Output is correct
6 Correct 1983 ms 126816 KB Output is correct
7 Correct 2182 ms 126932 KB Output is correct
8 Correct 2275 ms 126804 KB Output is correct
9 Correct 1487 ms 127060 KB Output is correct
10 Correct 1479 ms 126932 KB Output is correct
11 Correct 1248 ms 126932 KB Output is correct
12 Correct 1397 ms 126804 KB Output is correct
13 Correct 1690 ms 126848 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 113124 KB Output is correct
2 Correct 59 ms 113124 KB Output is correct
3 Correct 60 ms 113124 KB Output is correct
4 Correct 60 ms 113124 KB Output is correct
5 Correct 60 ms 113124 KB Output is correct
6 Correct 62 ms 113124 KB Output is correct
7 Correct 80 ms 114020 KB Output is correct
8 Correct 77 ms 114020 KB Output is correct
9 Correct 79 ms 114020 KB Output is correct
10 Correct 76 ms 114020 KB Output is correct
11 Correct 78 ms 114020 KB Output is correct
12 Correct 78 ms 114020 KB Output is correct
13 Correct 77 ms 114020 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 113124 KB Output is correct
2 Correct 60 ms 113124 KB Output is correct
3 Correct 62 ms 113124 KB Output is correct
4 Correct 61 ms 113124 KB Output is correct
5 Correct 65 ms 113124 KB Output is correct
6 Correct 1414 ms 127060 KB Output is correct
7 Correct 1806 ms 126932 KB Output is correct
8 Correct 2147 ms 126932 KB Output is correct
9 Correct 2251 ms 126928 KB Output is correct
10 Correct 1305 ms 126804 KB Output is correct
11 Correct 1833 ms 126768 KB Output is correct
12 Correct 1299 ms 126932 KB Output is correct
13 Correct 1475 ms 126936 KB Output is correct
14 Correct 1899 ms 126968 KB Output is correct
15 Correct 2136 ms 126932 KB Output is correct
16 Correct 1370 ms 126932 KB Output is correct
17 Correct 1417 ms 126932 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 113124 KB Output is correct
2 Correct 61 ms 113124 KB Output is correct
3 Correct 61 ms 113276 KB Output is correct
4 Correct 60 ms 113124 KB Output is correct
5 Correct 60 ms 113124 KB Output is correct
6 Correct 148 ms 116716 KB Output is correct
7 Correct 257 ms 117820 KB Output is correct
8 Correct 1126 ms 127124 KB Output is correct
9 Correct 1145 ms 127144 KB Output is correct
10 Correct 1176 ms 127316 KB Output is correct
11 Correct 1205 ms 127316 KB Output is correct
12 Correct 1226 ms 127188 KB Output is correct
13 Correct 1248 ms 127316 KB Output is correct
14 Correct 1227 ms 127312 KB Output is correct
15 Correct 61 ms 113124 KB Output is correct
16 Correct 62 ms 113124 KB Output is correct
17 Correct 59 ms 113124 KB Output is correct
18 Correct 59 ms 113124 KB Output is correct
19 Correct 59 ms 113124 KB Output is correct
20 Correct 67 ms 113252 KB Output is correct
21 Correct 161 ms 116704 KB Output is correct
22 Correct 61 ms 113124 KB Output is correct
23 Correct 68 ms 113252 KB Output is correct
24 Correct 163 ms 116796 KB Output is correct
25 Correct 179 ms 116576 KB Output is correct
26 Correct 165 ms 116832 KB Output is correct
27 Correct 162 ms 116660 KB Output is correct
28 Correct 279 ms 117568 KB Output is correct
29 Correct 2239 ms 126936 KB Output is correct
30 Correct 277 ms 117608 KB Output is correct
31 Correct 2229 ms 127188 KB Output is correct
32 Correct 1670 ms 126936 KB Output is correct
33 Correct 1656 ms 126856 KB Output is correct
34 Correct 2013 ms 126868 KB Output is correct
35 Correct 60 ms 113124 KB Output is correct
36 Correct 62 ms 113124 KB Output is correct
37 Correct 158 ms 116836 KB Output is correct
38 Correct 1411 ms 126932 KB Output is correct
39 Correct 1596 ms 126756 KB Output is correct
40 Correct 1983 ms 126816 KB Output is correct
41 Correct 2182 ms 126932 KB Output is correct
42 Correct 2275 ms 126804 KB Output is correct
43 Correct 1487 ms 127060 KB Output is correct
44 Correct 1479 ms 126932 KB Output is correct
45 Correct 1248 ms 126932 KB Output is correct
46 Correct 1397 ms 126804 KB Output is correct
47 Correct 1690 ms 126848 KB Output is correct
48 Correct 59 ms 113124 KB Output is correct
49 Correct 59 ms 113124 KB Output is correct
50 Correct 60 ms 113124 KB Output is correct
51 Correct 60 ms 113124 KB Output is correct
52 Correct 60 ms 113124 KB Output is correct
53 Correct 62 ms 113124 KB Output is correct
54 Correct 80 ms 114020 KB Output is correct
55 Correct 77 ms 114020 KB Output is correct
56 Correct 79 ms 114020 KB Output is correct
57 Correct 76 ms 114020 KB Output is correct
58 Correct 78 ms 114020 KB Output is correct
59 Correct 78 ms 114020 KB Output is correct
60 Correct 77 ms 114020 KB Output is correct
61 Correct 152 ms 116324 KB Output is correct
62 Correct 247 ms 117440 KB Output is correct
63 Correct 1276 ms 126932 KB Output is correct
64 Correct 1526 ms 126804 KB Output is correct
65 Correct 1903 ms 126804 KB Output is correct
66 Correct 2133 ms 126804 KB Output is correct
67 Correct 2277 ms 126932 KB Output is correct
68 Correct 1444 ms 126688 KB Output is correct
69 Correct 1806 ms 126680 KB Output is correct
70 Correct 1424 ms 126820 KB Output is correct
71 Correct 1630 ms 126804 KB Output is correct
72 Correct 2005 ms 126800 KB Output is correct
73 Correct 2263 ms 126548 KB Output is correct
74 Correct 1313 ms 126492 KB Output is correct
75 Correct 1516 ms 126684 KB Output is correct