oj.uz

Submission #434694

# Submission time Handle Problem Language Result Execution time Memory
434694 2021-06-21T15:00:28 Z frodakcin Comparing Plants (IOI20_plants) C++11
60 / 100
 2690 ms 125104 KB 
#include "plants.h"
#include <queue>
#include <bitset>

namespace SLOW_SOLN
{
	const int MN = 5e3+10;
	const int INF = 0x3f3f3f3f;

	int N, K, ts[MN], ctr;
	bool v[MN];
	std::vector<int> a[MN]; // i > a[i][...] -- dag
	std::bitset<MN> vis[MN];

	void dfs(int n)
	{
		v[n]=1;
		for(int x:a[n])
			if(!v[x])
				dfs(x);
		ts[ctr++]=n;
	}

	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;
				}
			for(int i=1;i<K;++i)
				if(r[(n+i)%N] >= 0)
					a[n].push_back((n+i)%N);
			for(int i=1;i<K;++i)
				if(r[(n-i+N)%N] >= 0)
					a[n].push_back((n-i+N)%N);
		}

		for(int i=0;i<N;++i)
			if(!v[i])
				dfs(i);

		for(int i=0;i<N;++i)
			vis[i].set(i);
		for(int i=0;i<N;++i)
			for(int x:a[ts[i]])
				vis[ts[i]]|=vis[x];
		return;
	}

	int compare_plants(int x, int y)
	{
		if(vis[x][y]) return 1;
		if(vis[y][x]) return -1;
		return 0;
	}
}

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();
	if(N <= 5000)
	{
		return SLOW_SOLN::init(k, r);
	}
	
	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(N <= 5000)
	{
		return SLOW_SOLN::compare_plants(x, 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 6092 KB Output is correct
2 Correct 3 ms 6092 KB Output is correct
3 Correct 4 ms 6092 KB Output is correct
4 Correct 4 ms 6092 KB Output is correct
5 Correct 4 ms 6092 KB Output is correct
6 Correct 67 ms 8812 KB Output is correct
7 Correct 116 ms 9672 KB Output is correct
8 Correct 454 ms 15432 KB Output is correct
9 Correct 442 ms 15328 KB Output is correct
10 Correct 462 ms 15236 KB Output is correct
11 Correct 390 ms 15324 KB Output is correct
12 Correct 382 ms 15460 KB Output is correct
13 Correct 355 ms 15284 KB Output is correct
14 Correct 416 ms 15360 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6092 KB Output is correct
2 Correct 4 ms 6092 KB Output is correct
3 Correct 3 ms 6092 KB Output is correct
4 Correct 4 ms 6092 KB Output is correct
5 Correct 5 ms 6092 KB Output is correct
6 Correct 89 ms 11384 KB Output is correct
7 Correct 2266 ms 104696 KB Output is correct
8 Correct 6 ms 6220 KB Output is correct
9 Correct 87 ms 11376 KB Output is correct
10 Correct 2177 ms 104744 KB Output is correct
11 Correct 1363 ms 73812 KB Output is correct
12 Correct 1461 ms 73588 KB Output is correct
13 Correct 2690 ms 125104 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6092 KB Output is correct
2 Correct 4 ms 6092 KB Output is correct
3 Correct 3 ms 6092 KB Output is correct
4 Correct 4 ms 6092 KB Output is correct
5 Correct 5 ms 6092 KB Output is correct
6 Correct 89 ms 11384 KB Output is correct
7 Correct 2266 ms 104696 KB Output is correct
8 Correct 6 ms 6220 KB Output is correct
9 Correct 87 ms 11376 KB Output is correct
10 Correct 2177 ms 104744 KB Output is correct
11 Correct 1363 ms 73812 KB Output is correct
12 Correct 1461 ms 73588 KB Output is correct
13 Correct 2690 ms 125104 KB Output is correct
14 Correct 128 ms 9704 KB Output is correct
15 Correct 690 ms 15784 KB Output is correct
16 Correct 114 ms 9792 KB Output is correct
17 Correct 763 ms 15784 KB Output is correct
18 Correct 497 ms 15764 KB Output is correct
19 Correct 499 ms 15872 KB Output is correct
20 Correct 695 ms 15764 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6092 KB Output is correct
2 Correct 4 ms 6092 KB Output is correct
3 Correct 75 ms 10260 KB Output is correct
4 Correct 407 ms 15732 KB Output is correct
5 Correct 530 ms 15868 KB Output is correct
6 Correct 696 ms 15884 KB Output is correct
7 Correct 676 ms 15916 KB Output is correct
8 Correct 721 ms 15908 KB Output is correct
9 Correct 439 ms 15840 KB Output is correct
10 Correct 488 ms 15944 KB Output is correct
11 Correct 361 ms 15328 KB Output is correct
12 Correct 405 ms 15772 KB Output is correct
13 Correct 477 ms 15760 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6092 KB Output is correct
2 Correct 4 ms 6092 KB Output is correct
3 Correct 4 ms 6092 KB Output is correct
4 Correct 4 ms 6092 KB Output is correct
5 Correct 4 ms 6092 KB Output is correct
6 Correct 7 ms 6224 KB Output is correct
7 Correct 18 ms 6860 KB Output is correct
8 Correct 21 ms 7068 KB Output is correct
9 Correct 23 ms 6852 KB Output is correct
10 Correct 22 ms 7024 KB Output is correct
11 Correct 18 ms 6860 KB Output is correct
12 Correct 19 ms 6940 KB Output is correct
13 Correct 27 ms 7364 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6092 KB Output is correct
2 Correct 4 ms 6092 KB Output is correct
3 Correct 3 ms 6092 KB Output is correct
4 Correct 3 ms 6092 KB Output is correct
5 Correct 15 ms 7244 KB Output is correct
6 Incorrect 561 ms 15824 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6092 KB Output is correct
2 Correct 3 ms 6092 KB Output is correct
3 Correct 4 ms 6092 KB Output is correct
4 Correct 4 ms 6092 KB Output is correct
5 Correct 4 ms 6092 KB Output is correct
6 Correct 67 ms 8812 KB Output is correct
7 Correct 116 ms 9672 KB Output is correct
8 Correct 454 ms 15432 KB Output is correct
9 Correct 442 ms 15328 KB Output is correct
10 Correct 462 ms 15236 KB Output is correct
11 Correct 390 ms 15324 KB Output is correct
12 Correct 382 ms 15460 KB Output is correct
13 Correct 355 ms 15284 KB Output is correct
14 Correct 416 ms 15360 KB Output is correct
15 Correct 3 ms 6092 KB Output is correct
16 Correct 4 ms 6092 KB Output is correct
17 Correct 3 ms 6092 KB Output is correct
18 Correct 4 ms 6092 KB Output is correct
19 Correct 5 ms 6092 KB Output is correct
20 Correct 89 ms 11384 KB Output is correct
21 Correct 2266 ms 104696 KB Output is correct
22 Correct 6 ms 6220 KB Output is correct
23 Correct 87 ms 11376 KB Output is correct
24 Correct 2177 ms 104744 KB Output is correct
25 Correct 1363 ms 73812 KB Output is correct
26 Correct 1461 ms 73588 KB Output is correct
27 Correct 2690 ms 125104 KB Output is correct
28 Correct 128 ms 9704 KB Output is correct
29 Correct 690 ms 15784 KB Output is correct
30 Correct 114 ms 9792 KB Output is correct
31 Correct 763 ms 15784 KB Output is correct
32 Correct 497 ms 15764 KB Output is correct
33 Correct 499 ms 15872 KB Output is correct
34 Correct 695 ms 15764 KB Output is correct
35 Correct 4 ms 6092 KB Output is correct
36 Correct 4 ms 6092 KB Output is correct
37 Correct 75 ms 10260 KB Output is correct
38 Correct 407 ms 15732 KB Output is correct
39 Correct 530 ms 15868 KB Output is correct
40 Correct 696 ms 15884 KB Output is correct
41 Correct 676 ms 15916 KB Output is correct
42 Correct 721 ms 15908 KB Output is correct
43 Correct 439 ms 15840 KB Output is correct
44 Correct 488 ms 15944 KB Output is correct
45 Correct 361 ms 15328 KB Output is correct
46 Correct 405 ms 15772 KB Output is correct
47 Correct 477 ms 15760 KB Output is correct
48 Correct 4 ms 6092 KB Output is correct
49 Correct 4 ms 6092 KB Output is correct
50 Correct 4 ms 6092 KB Output is correct
51 Correct 4 ms 6092 KB Output is correct
52 Correct 4 ms 6092 KB Output is correct
53 Correct 7 ms 6224 KB Output is correct
54 Correct 18 ms 6860 KB Output is correct
55 Correct 21 ms 7068 KB Output is correct
56 Correct 23 ms 6852 KB Output is correct
57 Correct 22 ms 7024 KB Output is correct
58 Correct 18 ms 6860 KB Output is correct
59 Correct 19 ms 6940 KB Output is correct
60 Correct 27 ms 7364 KB Output is correct
61 Correct 71 ms 10312 KB Output is correct
62 Incorrect 103 ms 9884 KB Output isn't correct
63 Halted 0 ms 0 KB -