oj.uz

Submission #434651

# Submission time Handle Problem Language Result Execution time Memory
434651 2021-06-21T13:55:31 Z frodakcin Comparing Plants (IOI20_plants) C++11
19 / 100
 4000 ms 11560 KB 
#include "plants.h"
#include <queue>
#include <bitset>

template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}

const int MN = 2e5+10;
const int INF = 0x3f3f3f3f;

int N, K, ts[MN], ctr, ord[MN];
bool v[MN];

//Minmax Segtree
struct minmax
{
	public:
		int min, max;
		minmax(int _mn=INF, int _mx=-INF): min(_mn), max(_mx) {}
		minmax& operator += (const int& o) {min += o, max += o; return *this;}
		minmax& operator -= (const int& o) {min -= o, max -= o; return *this;}
		minmax& operator += (const minmax& o) {ckmin(min, o.min); ckmax(max, o.max); return *this;}

		friend minmax operator + (minmax a, const int& b) {return a+=b;}
		friend minmax operator - (minmax a, const int& b) {return a-=b;}
		friend minmax operator + (minmax a, const minmax& b) {return a+=b;}

		bool contains(int x) {return min <= x && x <= max;}
} range[MN];
minmax mv[1 << 19];
minmax mqry(int n, int l, int r, int ql, int qr)
{
	if(ql <= l && r <= qr) return mv[n];
	else
	{
		int m=l+(r-l)/2; minmax f;
		if(ql < m) f += mqry(n<<1, l, m, ql, qr);
		if(m < qr) f += mqry(n<<1|1, m, r, ql, qr);
		return f;
	}
}
void mupd(int n, int l, int r, int q, minmax val)
{
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(q < m) mupd(n<<1, l, m, q, val);
		else mupd(n<<1|1, m, r, q, val);
		mv[n]=mv[n<<1]+mv[n<<1|1];
	}
	else
		mv[n]=val;
}

void init(int k, std::vector<int> r) {
	K=k, N=r.size();
	
	std::queue<int> q;
	int zc=0;
	for(int i=N-K;i<N;++i)
		zc += !r[i];
	for(int i=0;i<N;++i)
	{
		zc -= !r[(N-K+i)%N];
		if(zc==0 && r[i]==0)
			q.push(i);
		zc += !r[i];
	}

	for(;!q.empty();)
	{
		int n=q.front(); q.pop();
		if(r[n] < 0) continue;
		
		// check
		bool ok=1;
		for(int i=1;i<K;++i)
			if(r[(n-i+N)%N]==0)
				ok=0;
		if(!ok) continue;

		// add
		r[n]=-1;
		for(int i=K-1;i>0;--i)
			--r[(n-i+N)%N];
		for(int i=1;i<K;++i)
			if(r[(n+i)%N] == 0)
			{
				q.push((n+i)%N);
				break;
			}
		for(int i=K-1;i>0;--i)
			if(r[(n-i+N)%N] == 0)
			{
				q.push((n-i+N)%N);
				break;
			}

		//modify ans
		ts[ctr]=n;
		ord[n]=ctr++;
	}

	for(int i=N-1, n;i>=0;--i)
	{
		n=ts[i];
		range[n] = minmax(n, n);
		range[n] += mqry(1, 0, N, n-K+1, n+K);
		if(n+K>N) range[n] += mqry(1, 0, N, 0, n+K-N)+N;
		if(n-K+1<0) range[n] += mqry(1, 0, N, n-K+1+N, N)-N;
		mupd(1, 0, N, n, range[n]);
		//printf("%d: %d <-> %d\n", n, range[n].min, range[n].max);
	}
	return;
}

bool cover(int a, int b) // is a > b?
{
	if(ord[a]>ord[b]) return 0;
	return range[a].contains(b) || range[a].contains(b+N) || range[a].contains(b-N);
}

int compare_plants(int x, int y)
{
	if(cover(x, y)) return 1;
	if(cover(y, x)) return -1;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 3 ms 5964 KB Output is correct
5 Correct 3 ms 5964 KB Output is correct
6 Correct 79 ms 8808 KB Output is correct
7 Correct 108 ms 9016 KB Output is correct
8 Correct 199 ms 11512 KB Output is correct
9 Correct 205 ms 11372 KB Output is correct
10 Correct 201 ms 11332 KB Output is correct
11 Correct 210 ms 11392 KB Output is correct
12 Correct 174 ms 11392 KB Output is correct
13 Correct 173 ms 11512 KB Output is correct
14 Correct 178 ms 11332 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 4 ms 5964 KB Output is correct
3 Correct 4 ms 5964 KB Output is correct
4 Correct 4 ms 5964 KB Output is correct
5 Correct 4 ms 5964 KB Output is correct
6 Correct 21 ms 6032 KB Output is correct
7 Correct 469 ms 8768 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 22 ms 6028 KB Output is correct
10 Correct 463 ms 9016 KB Output is correct
11 Correct 303 ms 8772 KB Output is correct
12 Correct 381 ms 8972 KB Output is correct
13 Correct 526 ms 8764 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 4 ms 5964 KB Output is correct
3 Correct 4 ms 5964 KB Output is correct
4 Correct 4 ms 5964 KB Output is correct
5 Correct 4 ms 5964 KB Output is correct
6 Correct 21 ms 6032 KB Output is correct
7 Correct 469 ms 8768 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 22 ms 6028 KB Output is correct
10 Correct 463 ms 9016 KB Output is correct
11 Correct 303 ms 8772 KB Output is correct
12 Correct 381 ms 8972 KB Output is correct
13 Correct 526 ms 8764 KB Output is correct
14 Execution timed out 4038 ms 8716 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5960 KB Output is correct
2 Correct 8 ms 5928 KB Output is correct
3 Correct 74 ms 8704 KB Output is correct
4 Correct 222 ms 11364 KB Output is correct
5 Correct 635 ms 11560 KB Output is correct
6 Execution timed out 4078 ms 11384 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 4 ms 5964 KB Output is correct
3 Correct 3 ms 5964 KB Output is correct
4 Correct 4 ms 5964 KB Output is correct
5 Incorrect 4 ms 5964 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 4 ms 5964 KB Output is correct
3 Correct 3 ms 5964 KB Output is correct
4 Correct 5 ms 5836 KB Output is correct
5 Incorrect 6 ms 5964 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5836 KB Output is correct
2 Correct 3 ms 5836 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 3 ms 5964 KB Output is correct
5 Correct 3 ms 5964 KB Output is correct
6 Correct 79 ms 8808 KB Output is correct
7 Correct 108 ms 9016 KB Output is correct
8 Correct 199 ms 11512 KB Output is correct
9 Correct 205 ms 11372 KB Output is correct
10 Correct 201 ms 11332 KB Output is correct
11 Correct 210 ms 11392 KB Output is correct
12 Correct 174 ms 11392 KB Output is correct
13 Correct 173 ms 11512 KB Output is correct
14 Correct 178 ms 11332 KB Output is correct
15 Correct 4 ms 5964 KB Output is correct
16 Correct 4 ms 5964 KB Output is correct
17 Correct 4 ms 5964 KB Output is correct
18 Correct 4 ms 5964 KB Output is correct
19 Correct 4 ms 5964 KB Output is correct
20 Correct 21 ms 6032 KB Output is correct
21 Correct 469 ms 8768 KB Output is correct
22 Correct 5 ms 5964 KB Output is correct
23 Correct 22 ms 6028 KB Output is correct
24 Correct 463 ms 9016 KB Output is correct
25 Correct 303 ms 8772 KB Output is correct
26 Correct 381 ms 8972 KB Output is correct
27 Correct 526 ms 8764 KB Output is correct
28 Execution timed out 4038 ms 8716 KB Time limit exceeded
29 Halted 0 ms 0 KB -