oj.uz

Submission #317658

# Submission time Handle Problem Language Result Execution time Memory
317658 2020-10-30T06:13:13 Z arnold518 Comparing Plants (IOI20_plants) C++14
27 / 100
 2149 ms 51248 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;

vector<int> adj[MAXN+10];
int LL[MAXN+10], RR[MAXN+10], dfn;

void dfs(int now)
{
	LL[now]=++dfn;
	for(int nxt : adj[now]) dfs(nxt);
	RR[now]=dfn;
}

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);
	vector<int> root;
	for(int i=0; i<V.size(); i++)
	{
		int now=V[i].second;
		pii t=min(seg3.query(now-K+1, now), seg3.query(now, now+K-1));

		if(t.first!=INF) adj[t.second].push_back(now);
		else root.push_back(now);
		seg3.update2(now, H[now]);
	}
	for(auto it : root) dfs(it);
	return;
}

int compare_plants(int x, int y)
{
	if(LL[x]<=LL[y] && RR[y]<=RR[x]) return 1;
	if(LL[y]<=LL[x] && RR[x]<=RR[y]) 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:177: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]
  177 |  for(int i=0; i<V.size(); i++)
      |               ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 14 ms 23808 KB Output is correct
4 Incorrect 14 ms 23808 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23936 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 14 ms 23808 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 110 ms 27388 KB Output is correct
8 Correct 17 ms 23936 KB Output is correct
9 Correct 21 ms 24064 KB Output is correct
10 Correct 114 ms 27512 KB Output is correct
11 Correct 103 ms 27384 KB Output is correct
12 Correct 102 ms 27512 KB Output is correct
13 Correct 108 ms 27384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23936 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 14 ms 23808 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 110 ms 27388 KB Output is correct
8 Correct 17 ms 23936 KB Output is correct
9 Correct 21 ms 24064 KB Output is correct
10 Correct 114 ms 27512 KB Output is correct
11 Correct 103 ms 27384 KB Output is correct
12 Correct 102 ms 27512 KB Output is correct
13 Correct 108 ms 27384 KB Output is correct
14 Correct 219 ms 29140 KB Output is correct
15 Correct 2149 ms 51176 KB Output is correct
16 Correct 218 ms 29140 KB Output is correct
17 Correct 2144 ms 51164 KB Output is correct
18 Correct 1378 ms 51176 KB Output is correct
19 Correct 1349 ms 51248 KB Output is correct
20 Correct 1930 ms 51176 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Incorrect 93 ms 26872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 14 ms 23808 KB Output is correct
3 Incorrect 15 ms 23936 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 14 ms 23808 KB Output is correct
4 Incorrect 14 ms 23808 KB Output isn't correct
5 Halted 0 ms 0 KB -