oj.uz

Submission #434690

# Submission time Handle Problem Language Result Execution time Memory
434690 2021-06-21T14:58:04 Z frodakcin Comparing Plants (IOI20_plants) C++11
49 / 100
 800 ms 16196 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], done[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;}
		bool contains(const minmax& x) {return min <= x.min && x.max <= 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;
}

//R segment tree
int rv[1 << 19], rz[1 << 19];
void rupd(int n, int x) {rv[n] += x, rz[n] += x;}
void rdown(int n)
{
	if(rz[n])
	{
		rupd(n<<1, rz[n]);
		rupd(n<<1|1, rz[n]);
		rz[n]=0;
	}
}
void rupd(int n, int l, int r, int ql, int qr, int x)
{
	if(ql <= l&&r <= qr) rupd(n, x);
	else
	{
		int m=l+(r-l)/2;
		rdown(n);
		if(ql < m) rupd(n<<1, l, m, ql, qr, x);
		if(m < qr) rupd(n<<1|1, m, r, ql, qr, x);
		rv[n] = std::min(rv[n<<1], rv[n<<1|1]);
	}
}
int rqry(int n, int l, int r, int ql) // return leftmost zero
{
	if(rv[n] > 0) return r;
	else if(r-l>1)
	{
		int m=l+(r-l)/2, f=m;
		rdown(n);
		if(ql < m) f=rqry(n<<1, l, m, ql);
		if(f == m) f=rqry(n<<1|1, m, r, ql);
		return f;
	}
	else return l;
}

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(int i=0;i<N;++i)
		rupd(1, 0, N, i, i+1, r[i]);

	for(;!q.empty();)
	{
		int n=q.front(); q.pop();
		if(done[n]) continue;
		
		// check
		int loc = rqry(1, 0, N, n-K+1);
		//printf("?? %d (%d)\n", n, loc);
		if(loc < n) continue;
		if(n-K+1 < 0 && rqry(1, 0, N, n-K+1+N) < N) continue;

		// add
		rupd(1, 0, N, n, n+1, INF);
		//printf("TEST [%d] %d\n", n, rqry(1, 0, N, 0));

		rupd(1, 0, N, n-K+1, n, -1);
		if(n-K+1 < 0) rupd(1, 0, N, n-K+1+N, N, -1);

		loc = rqry(1, 0, N, n);
		if(loc < std::min(N, n+K))
			q.push(loc);
		else if(n+K>N)
		{
			loc = rqry(1, 0, N, 0);
			if(loc<n+K-N)
				q.push(loc);
		}

		loc = N;
		if(n-K+1 < 0)
			loc = rqry(1, 0, N, n-K+1+N);
		if(loc < N)
			q.push(loc);
		else
		{
			loc = rqry(1, 0, N, n-K+1);
			if(loc < n)
				q.push(loc);
		}

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

	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(range[b]) || range[a].contains(range[b]+N) || range[a].contains(range[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 4 ms 5964 KB Output is correct
2 Correct 3 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 5976 KB Output is correct
6 Correct 72 ms 8692 KB Output is correct
7 Correct 127 ms 9552 KB Output is correct
8 Correct 420 ms 15316 KB Output is correct
9 Correct 455 ms 15164 KB Output is correct
10 Correct 421 ms 15228 KB Output is correct
11 Correct 396 ms 15208 KB Output is correct
12 Correct 365 ms 15112 KB Output is correct
13 Correct 357 ms 15236 KB Output is correct
14 Correct 396 ms 15192 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 5964 KB Output is correct
5 Correct 4 ms 5964 KB Output is correct
6 Correct 7 ms 5964 KB Output is correct
7 Correct 92 ms 9276 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 7 ms 5964 KB Output is correct
10 Correct 81 ms 9252 KB Output is correct
11 Correct 73 ms 9124 KB Output is correct
12 Correct 73 ms 9368 KB Output is correct
13 Correct 81 ms 9364 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 5964 KB Output is correct
5 Correct 4 ms 5964 KB Output is correct
6 Correct 7 ms 5964 KB Output is correct
7 Correct 92 ms 9276 KB Output is correct
8 Correct 5 ms 5964 KB Output is correct
9 Correct 7 ms 5964 KB Output is correct
10 Correct 81 ms 9252 KB Output is correct
11 Correct 73 ms 9124 KB Output is correct
12 Correct 73 ms 9368 KB Output is correct
13 Correct 81 ms 9364 KB Output is correct
14 Correct 116 ms 10192 KB Output is correct
15 Correct 733 ms 16040 KB Output is correct
16 Correct 118 ms 9560 KB Output is correct
17 Correct 737 ms 16196 KB Output is correct
18 Correct 502 ms 15996 KB Output is correct
19 Correct 492 ms 15992 KB Output is correct
20 Correct 800 ms 16000 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5964 KB Output is correct
2 Correct 4 ms 5964 KB Output is correct
3 Correct 72 ms 8840 KB Output is correct
4 Correct 400 ms 15828 KB Output is correct
5 Correct 499 ms 15988 KB Output is correct
6 Correct 645 ms 16012 KB Output is correct
7 Correct 731 ms 15904 KB Output is correct
8 Correct 693 ms 15920 KB Output is correct
9 Correct 441 ms 15904 KB Output is correct
10 Correct 448 ms 15876 KB Output is correct
11 Correct 418 ms 15220 KB Output is correct
12 Correct 437 ms 15876 KB Output is correct
13 Correct 516 ms 16000 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5964 KB Output is correct
2 Correct 3 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 4 ms 5964 KB Output is correct
4 Correct 3 ms 5964 KB Output is correct
5 Incorrect 5 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 4 ms 5964 KB Output is correct
2 Correct 3 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 5976 KB Output is correct
6 Correct 72 ms 8692 KB Output is correct
7 Correct 127 ms 9552 KB Output is correct
8 Correct 420 ms 15316 KB Output is correct
9 Correct 455 ms 15164 KB Output is correct
10 Correct 421 ms 15228 KB Output is correct
11 Correct 396 ms 15208 KB Output is correct
12 Correct 365 ms 15112 KB Output is correct
13 Correct 357 ms 15236 KB Output is correct
14 Correct 396 ms 15192 KB Output is correct
15 Correct 3 ms 5964 KB Output is correct
16 Correct 4 ms 5964 KB Output is correct
17 Correct 3 ms 5964 KB Output is correct
18 Correct 5 ms 5964 KB Output is correct
19 Correct 4 ms 5964 KB Output is correct
20 Correct 7 ms 5964 KB Output is correct
21 Correct 92 ms 9276 KB Output is correct
22 Correct 5 ms 5964 KB Output is correct
23 Correct 7 ms 5964 KB Output is correct
24 Correct 81 ms 9252 KB Output is correct
25 Correct 73 ms 9124 KB Output is correct
26 Correct 73 ms 9368 KB Output is correct
27 Correct 81 ms 9364 KB Output is correct
28 Correct 116 ms 10192 KB Output is correct
29 Correct 733 ms 16040 KB Output is correct
30 Correct 118 ms 9560 KB Output is correct
31 Correct 737 ms 16196 KB Output is correct
32 Correct 502 ms 15996 KB Output is correct
33 Correct 492 ms 15992 KB Output is correct
34 Correct 800 ms 16000 KB Output is correct
35 Correct 3 ms 5964 KB Output is correct
36 Correct 4 ms 5964 KB Output is correct
37 Correct 72 ms 8840 KB Output is correct
38 Correct 400 ms 15828 KB Output is correct
39 Correct 499 ms 15988 KB Output is correct
40 Correct 645 ms 16012 KB Output is correct
41 Correct 731 ms 15904 KB Output is correct
42 Correct 693 ms 15920 KB Output is correct
43 Correct 441 ms 15904 KB Output is correct
44 Correct 448 ms 15876 KB Output is correct
45 Correct 418 ms 15220 KB Output is correct
46 Correct 437 ms 15876 KB Output is correct
47 Correct 516 ms 16000 KB Output is correct
48 Correct 4 ms 5964 KB Output is correct
49 Correct 3 ms 5964 KB Output is correct
50 Correct 3 ms 5964 KB Output is correct
51 Correct 4 ms 5964 KB Output is correct
52 Incorrect 4 ms 5964 KB Output isn't correct
53 Halted 0 ms 0 KB -