oj.uz

Submission #434630

# Submission time Handle Problem Language Result Execution time Memory
434630 2021-06-21T13:29:36 Z frodakcin Comparing Plants (IOI20_plants) C++11
14 / 100
 4000 ms 8996 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, 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 r;
	}
}
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
		ord[n]=ctr++;
		range[n] = minmax(n-K+1, n+K-1);
		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)
{
	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
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 3 ms 5848 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 3 ms 5836 KB Output is correct
5 Correct 4 ms 5964 KB Output is correct
6 Correct 22 ms 5964 KB Output is correct
7 Correct 456 ms 8748 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 21 ms 6020 KB Output is correct
10 Correct 470 ms 8752 KB Output is correct
11 Correct 294 ms 8708 KB Output is correct
12 Correct 390 ms 8996 KB Output is correct
13 Correct 535 ms 8764 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 3 ms 5848 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 3 ms 5836 KB Output is correct
5 Correct 4 ms 5964 KB Output is correct
6 Correct 22 ms 5964 KB Output is correct
7 Correct 456 ms 8748 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 21 ms 6020 KB Output is correct
10 Correct 470 ms 8752 KB Output is correct
11 Correct 294 ms 8708 KB Output is correct
12 Correct 390 ms 8996 KB Output is correct
13 Correct 535 ms 8764 KB Output is correct
14 Execution timed out 4046 ms 8516 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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