oj.uz

Submission #433756

# Submission time Handle Problem Language Result Execution time Memory
433756 2021-06-20T10:24:22 Z arayi Comparing Plants (IOI20_plants) C++17
27 / 100
 1131 ms 18600 KB 
#include "plants.h"
#include <cassert>
#include <vector>
#include <iostream>
#define ad push_back
using namespace std;

const int N = 1e6 + 30;
int n, k;
int a[N];
int t1[4*N], flg1[4*N];
void push1(int nd)
{
	flg1[nd*2]+=flg1[nd];
	flg1[nd*2+1]+=flg1[nd];
	t1[nd]+=flg1[nd];
	flg1[nd] = 0;
}
void upd1(int l, int r, int v, int nl = 0, int nr = n - 1, int nd = 1)
{
	push1(nd);
	if(l > nr || r < nl) return;
	if(l == nl && r == nr)
	{
		flg1[nd] += v;
		push1(nd);
		return;
	}
	int md = (nl + nr)/2;
	upd1(l,min(md, r), v, nl, md, nd*2);
	upd1(max(md + 1, l), r, v, md + 1, nr, nd*2+1);
	t1[nd]=min(t1[nd*2], t1[nd*2+1]);
}
int qry1(int l = 0, int r = n - 1, int nd = 1)
{
	if(l==r) return l;
	push1(nd*2), push1(nd*2+1);
	int md = (l + r) / 2;
	if(t1[nd*2] <= t1[nd*2+1]) return qry1(l, md, nd*2);
	return qry1(md + 1, r, nd * 2 + 1);
}
int t[4*N], flg[4*N];
void push(int nd)
{
	flg[nd*2]+=flg[nd];
	flg[nd*2+1]+=flg[nd];
	t[nd]+=flg[nd];
	flg[nd] = 0;
}
void upd(int l, int r, int v, int nl = 0, int nr = n - 1, int nd = 1)
{
	push(nd);
	if(l > nr || r < nl) return;
	if(l == nl && r == nr)
	{
		flg[nd] += v;
		push(nd);
		return;
	}
	int md = (nl + nr)/2;
	upd(l,min(md, r), v, nl, md, nd*2);
	upd(max(md + 1, l), r, v, md + 1, nr, nd*2+1);
	t[nd]=min(t[nd*2], t[nd*2+1]);
}
int qry(int l = 0, int r = n - 1, int nd = 1)
{
	if(l==r) return l;
	push(nd*2), push(nd*2+1);
	int md = (l + r) / 2;
	if(t[nd*2] <= t[nd*2+1]) return qry(l, md, nd*2);
	return qry(md + 1, r, nd * 2 + 1);
}
int qu(int i, int l = 0, int r = n - 1, int nd = 1)
{
	push(nd);
	if(l > i || r < i) return 0;
	if(l == r) return t[nd];
	int md = (l + r) / 2;
	return qu(i, l, md, nd*2) + qu(i, md+1, r, nd*2+1);
}
int col[N];
void init(int k, std::vector<int> r) 
{
	k--;
	n = r.size();
	for (int i = 0; i < n; i++)
	{
		upd(i,i,r[i]);
		upd1(i,i,r[i]);
	}	
	for (int i = n - 1; i >= 0; i--)
	{
		push1(1);
		vector <int> fp;
		while(t1[1] == 0)
		{
			fp.ad(qry1());
			upd1(fp.back(), fp.back(), n+n+n);
			push1(1);
		}
		for(auto p : fp)
		{
			//cout << p << " ";
			int r = p + k;	
			col[p]=1;
			if(2*k+1<n)
			{
				upd1(p + 1, min(n-1,r), 1); upd(p + 1, min(n-1,r), 1); 
				upd1(0, r-n, 1); upd(0, r-n, 1);
			}
			else
			{
				int l = p - k;
				upd(max(0, l), p, -1); upd1(max(0, l), p, -1);
				upd(n+l, n-1, -1); upd1(n+l, n-1, -1);
				upd(0,n-1,1), upd1(0,n-1,1);
			}
		}
		//cout << endl;
		push(1);
		assert(t[1] <= 0);
		int i1 = qry();
		a[i1] = i;
		int l = i1-k, r = i1+k;
		if(r-l+1>=n) upd(0,n-1,-1), upd1(0,n-1,-1);
		else 
		{
			if(l < 0) 
			{
				upd(0,r,-1), upd1(0,r,-1);
				upd(n+l,n-1,-1), upd1(n+l,n-1,-1);
			}
			else if(r > n-1)
			{
				upd(l,n-1,-1), upd1(l,n-1,-1);
				upd(0,r-n,-1), upd1(0,r-n,-1);
			}
			else upd(l,r,-1), upd1(l,r,-1);
		}
		upd(i1,i1,n+n+n);
		//cout << i1 << endl;
		//for (int i = 0; i < n; i++) cout << qu(i) << " ";
		//cout << endl;		
	}
	//for (int i = 0; i < n; i++) cout << a[i] << " "; cout << endl;
	return;
}

int compare_plants(int x, int y) 
{
	if(a[x] > a[y]) return 1;	
	return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 1 ms 332 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 75 ms 3568 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 74 ms 3568 KB Output is correct
11 Correct 71 ms 3524 KB Output is correct
12 Correct 72 ms 3664 KB Output is correct
13 Correct 84 ms 3572 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 75 ms 3568 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 74 ms 3568 KB Output is correct
11 Correct 71 ms 3524 KB Output is correct
12 Correct 72 ms 3664 KB Output is correct
13 Correct 84 ms 3572 KB Output is correct
14 Correct 130 ms 5032 KB Output is correct
15 Correct 1125 ms 18224 KB Output is correct
16 Correct 129 ms 4916 KB Output is correct
17 Correct 1131 ms 18136 KB Output is correct
18 Correct 808 ms 18600 KB Output is correct
19 Correct 831 ms 18140 KB Output is correct
20 Correct 1109 ms 18128 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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