oj.uz

Submission #434426

# Submission time Handle Problem Language Result Execution time Memory
434426 2021-06-21T09:37:31 Z arayi Comparing Plants (IOI20_plants) C++17
44 / 100
 1275 ms 21228 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 tp()
{
	for (int i = 0; i < n; i++) cout << t[i] << " ";
	cout << endl;
}
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--)
	{
		//cout << i << endl;
		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)
		{
			int r = p + k;
			if(2*k+1<n)
			{
				upd(p + 1, min(n-1,r), 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);
			}
		}
		push(1);
		int i1 = qry();
		if(t[1] != 0) {assert(0);}
		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), upd(n+l,n-1,-1), upd1(0,i1,-1), upd1(n+l,n-1,-1);
			else if(r > n-1) upd(l,n-1,-1), upd(0,r-n,-1), upd1(l,i1,-1);
			else upd(l,r,-1), upd1(l,i1,-1);

		}	
		upd(i1,i1,n+n+n);
	}
	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 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 74 ms 5480 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 75 ms 5480 KB Output is correct
11 Correct 74 ms 5444 KB Output is correct
12 Correct 71 ms 5592 KB Output is correct
13 Correct 75 ms 5392 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 74 ms 5480 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 75 ms 5480 KB Output is correct
11 Correct 74 ms 5444 KB Output is correct
12 Correct 71 ms 5592 KB Output is correct
13 Correct 75 ms 5392 KB Output is correct
14 Correct 128 ms 7068 KB Output is correct
15 Correct 1068 ms 21168 KB Output is correct
16 Correct 132 ms 7108 KB Output is correct
17 Correct 1081 ms 21056 KB Output is correct
18 Correct 853 ms 21228 KB Output is correct
19 Correct 889 ms 21088 KB Output is correct
20 Correct 970 ms 21116 KB Output is correct

Subtask #4
17.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 Correct 64 ms 4952 KB Output is correct
4 Correct 752 ms 20412 KB Output is correct
5 Correct 841 ms 20560 KB Output is correct
6 Correct 1073 ms 20664 KB Output is correct
7 Correct 1218 ms 20820 KB Output is correct
8 Correct 1275 ms 21052 KB Output is correct
9 Correct 777 ms 20480 KB Output is correct
10 Correct 787 ms 20312 KB Output is correct
11 Correct 706 ms 20544 KB Output is correct
12 Correct 803 ms 20412 KB Output is correct
13 Correct 940 ms 20796 KB Output is correct

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 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 300 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 1 ms 332 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -