oj.uz

Submission #433622

# Submission time Handle Problem Language Result Execution time Memory
433622 2021-06-20T08:38:42 Z arayi Comparing Plants (IOI20_plants) C++17
14 / 100
 573 ms 19024 KB 
#include "plants.h"
#include <vector>
#include <iostream>
#define ad push_back
using namespace std;

const int N = 2e5 + 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>=n) upd(0,n-1,-1), upd1(0,n-1,-1);
		else 
		{
			upd(max(0, l), i1, -1); upd1(max(0, l), i1, -1);
			upd(n+l, n-1, -1); upd1(n+l, n-1, -1);
			upd(i1, min(n-1,r), -1); upd1(i1, min(n-1,r), -1);
			upd(0, r-n, -1); upd1(0, r-n, -1);
		}
		upd(i1,i1,n+n), upd1(i1,i1,n+1);
		//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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Incorrect 1 ms 204 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 2 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 85 ms 3564 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 78 ms 3576 KB Output is correct
11 Correct 79 ms 3504 KB Output is correct
12 Correct 113 ms 3688 KB Output is correct
13 Correct 87 ms 3568 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 85 ms 3564 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 5 ms 460 KB Output is correct
10 Correct 78 ms 3576 KB Output is correct
11 Correct 79 ms 3504 KB Output is correct
12 Correct 113 ms 3688 KB Output is correct
13 Correct 87 ms 3568 KB Output is correct
14 Correct 143 ms 4840 KB Output is correct
15 Incorrect 573 ms 19024 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 66 ms 3280 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 204 KB Output is correct
2 Correct 0 ms 332 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 0 ms 204 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 216 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -