oj.uz

Submission #433631

# Submission time Handle Problem Language Result Execution time Memory
433631 2021-06-20T08:49:29 Z arayi Comparing Plants (IOI20_plants) C++17
27 / 100
 1083 ms 18000 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;
		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 0 ms 332 KB Output is correct
3 Correct 1 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 73 ms 3652 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 73 ms 3568 KB Output is correct
11 Correct 74 ms 3524 KB Output is correct
12 Correct 72 ms 3668 KB Output is correct
13 Correct 77 ms 3576 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 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 73 ms 3652 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 73 ms 3568 KB Output is correct
11 Correct 74 ms 3524 KB Output is correct
12 Correct 72 ms 3668 KB Output is correct
13 Correct 77 ms 3576 KB Output is correct
14 Correct 166 ms 4844 KB Output is correct
15 Correct 1083 ms 17240 KB Output is correct
16 Correct 129 ms 4908 KB Output is correct
17 Correct 1070 ms 17392 KB Output is correct
18 Correct 819 ms 18000 KB Output is correct
19 Correct 813 ms 17392 KB Output is correct
20 Correct 989 ms 17344 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 204 KB Output is correct
3 Runtime error 47 ms 5468 KB Execution killed with signal 6
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 0 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 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 0 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -