oj.uz

Submission #433662

# Submission time Handle Problem Language Result Execution time Memory
433662 2021-06-20T09:19:51 Z arayi Comparing Plants (IOI20_plants) C++17
27 / 100
 1056 ms 17888 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);
}
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;
		assert(t1[1] >= 0);
		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);
		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);
		//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 332 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 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 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 3524 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 4 ms 440 KB Output is correct
10 Correct 77 ms 3556 KB Output is correct
11 Correct 70 ms 3524 KB Output is correct
12 Correct 72 ms 3700 KB Output is correct
13 Correct 74 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 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 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 3524 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 4 ms 440 KB Output is correct
10 Correct 77 ms 3556 KB Output is correct
11 Correct 70 ms 3524 KB Output is correct
12 Correct 72 ms 3700 KB Output is correct
13 Correct 74 ms 3572 KB Output is correct
14 Correct 137 ms 4916 KB Output is correct
15 Correct 1052 ms 17340 KB Output is correct
16 Correct 132 ms 5040 KB Output is correct
17 Correct 1056 ms 17348 KB Output is correct
18 Correct 812 ms 17888 KB Output is correct
19 Correct 817 ms 17252 KB Output is correct
20 Correct 979 ms 17348 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 0 ms 332 KB Output is correct
3 Incorrect 66 ms 3164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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