oj.uz

Submission #433627

# Submission time Handle Problem Language Result Execution time Memory
433627 2021-06-20T08:47:27 Z arayi Comparing Plants (IOI20_plants) C++17
27 / 100
 1126 ms 17856 KB 
#include "plants.h"
#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);
}
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);
			push1(1);
		}
		for(auto p : fp)
		{
			//cout << p << " ";
			int r = p + k;
			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);
		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);
		//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 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 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 0 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 3572 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 75 ms 3524 KB Output is correct
11 Correct 70 ms 3428 KB Output is correct
12 Correct 74 ms 3652 KB Output is correct
13 Correct 74 ms 3560 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 3572 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 75 ms 3524 KB Output is correct
11 Correct 70 ms 3428 KB Output is correct
12 Correct 74 ms 3652 KB Output is correct
13 Correct 74 ms 3560 KB Output is correct
14 Correct 132 ms 4896 KB Output is correct
15 Correct 1126 ms 17388 KB Output is correct
16 Correct 129 ms 4932 KB Output is correct
17 Correct 1123 ms 17336 KB Output is correct
18 Correct 816 ms 17856 KB Output is correct
19 Correct 874 ms 17308 KB Output is correct
20 Correct 1010 ms 17352 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 65 ms 3176 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 204 KB Output is correct
3 Incorrect 1 ms 204 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 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -