oj.uz

Submission #434635

# Submission time Handle Problem Language Result Execution time Memory
434635 2021-06-21T13:33:20 Z frodakcin Comparing Plants (IOI20_plants) C++11
14 / 100
 4000 ms 8968 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) // 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
0 / 5.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 Correct 4 ms 5912 KB Output is correct
4 Correct 4 ms 5836 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 4 ms 5836 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 4 ms 5836 KB Output is correct
5 Correct 5 ms 5836 KB Output is correct
6 Correct 22 ms 6020 KB Output is correct
7 Correct 461 ms 8824 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 22 ms 6020 KB Output is correct
10 Correct 476 ms 8760 KB Output is correct
11 Correct 296 ms 8712 KB Output is correct
12 Correct 367 ms 8968 KB Output is correct
13 Correct 520 ms 8900 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 4 ms 5836 KB Output is correct
3 Correct 4 ms 5836 KB Output is correct
4 Correct 4 ms 5836 KB Output is correct
5 Correct 5 ms 5836 KB Output is correct
6 Correct 22 ms 6020 KB Output is correct
7 Correct 461 ms 8824 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 22 ms 6020 KB Output is correct
10 Correct 476 ms 8760 KB Output is correct
11 Correct 296 ms 8712 KB Output is correct
12 Correct 367 ms 8968 KB Output is correct
13 Correct 520 ms 8900 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 3 ms 5836 KB Output is correct
3 Incorrect 71 ms 8696 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 5952 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 4 ms 5836 KB Output is correct
3 Correct 4 ms 5912 KB Output is correct
4 Correct 4 ms 5836 KB Output is correct
5 Incorrect 4 ms 5836 KB Output isn't correct
6 Halted 0 ms 0 KB -