oj.uz

Submission #317575

# Submission time Handle Problem Language Result Execution time Memory
317575 2020-10-30T02:43:06 Z arnold518 Comparing Plants (IOI20_plants) C++14
44 / 100
 1636 ms 25848 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 = 1e9;

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]);
	}
	int query(int node, int tl, int tr, int l, int r)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r) return tree[node].first;
		if(r<tl || tr<l) return INF;
		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);
	}
	int 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;

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();

	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;
		int now=seg1.tree[1].second; H[now]=i;
		assert(seg2.query(now-K+1, now-1)>=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)
		{
			//printf("!%d\n", it);
			seg1.update(it+1, it+K-1, 1);
		}

		//for(int j=0; j<N; j++) printf("%d ", seg1.query(j, j)); printf(" : seg1\n");
		//for(int j=0; j<N; j++) printf("%d ", seg2.query(j, j)); printf(" : seg2\n");
	}
	//for(int i=0; i<N; i++) printf("%d ", H[i]); printf("\n");
	return;
}

int compare_plants(int x, int y)
{
	int ans=0;
	if(H[x]>H[y]) return 1;
	if(H[x]<H[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 'int 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 'int compare_plants(int, int)':
plants.cpp:171:6: warning: unused variable 'ans' [-Wunused-variable]
  171 |  int ans=0;
      |      ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12800 KB Output is correct
2 Correct 8 ms 12800 KB Output is correct
3 Correct 8 ms 12800 KB Output is correct
4 Incorrect 8 ms 12800 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 8 ms 12800 KB Output is correct
2 Correct 8 ms 12800 KB Output is correct
3 Correct 8 ms 12800 KB Output is correct
4 Correct 8 ms 12800 KB Output is correct
5 Correct 8 ms 12800 KB Output is correct
6 Correct 13 ms 12928 KB Output is correct
7 Correct 99 ms 15992 KB Output is correct
8 Correct 10 ms 12928 KB Output is correct
9 Correct 13 ms 12928 KB Output is correct
10 Correct 119 ms 15992 KB Output is correct
11 Correct 91 ms 15864 KB Output is correct
12 Correct 94 ms 16056 KB Output is correct
13 Correct 99 ms 15964 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12800 KB Output is correct
2 Correct 8 ms 12800 KB Output is correct
3 Correct 8 ms 12800 KB Output is correct
4 Correct 8 ms 12800 KB Output is correct
5 Correct 8 ms 12800 KB Output is correct
6 Correct 13 ms 12928 KB Output is correct
7 Correct 99 ms 15992 KB Output is correct
8 Correct 10 ms 12928 KB Output is correct
9 Correct 13 ms 12928 KB Output is correct
10 Correct 119 ms 15992 KB Output is correct
11 Correct 91 ms 15864 KB Output is correct
12 Correct 94 ms 16056 KB Output is correct
13 Correct 99 ms 15964 KB Output is correct
14 Correct 196 ms 16556 KB Output is correct
15 Correct 1613 ms 22520 KB Output is correct
16 Correct 185 ms 16508 KB Output is correct
17 Correct 1618 ms 22520 KB Output is correct
18 Correct 1092 ms 22520 KB Output is correct
19 Correct 1071 ms 22520 KB Output is correct
20 Correct 1416 ms 22520 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12800 KB Output is correct
2 Correct 8 ms 12800 KB Output is correct
3 Correct 85 ms 15864 KB Output is correct
4 Correct 802 ms 22508 KB Output is correct
5 Correct 981 ms 22532 KB Output is correct
6 Correct 1313 ms 22504 KB Output is correct
7 Correct 1591 ms 22460 KB Output is correct
8 Correct 1636 ms 22520 KB Output is correct
9 Correct 868 ms 22776 KB Output is correct
10 Correct 863 ms 22520 KB Output is correct
11 Correct 685 ms 25464 KB Output is correct
12 Correct 839 ms 25720 KB Output is correct
13 Correct 1056 ms 25848 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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