oj.uz

Submission #373422

# Submission time Handle Problem Language Result Execution time Memory
373422 2021-03-04T14:19:54 Z pit4h Comparing Plants (IOI20_plants) C++14
27 / 100
 1537 ms 80748 KB 
#include "plants.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using pii = pair<int, int>;

const int MAXN = 2e5+1, base = (1<<18);
int n, k, when[MAXN], nr;
int ptr[MAXN], ptrr[MAXN];
vector<int> R;

pii tree_max[2*base+1];
void upd(int x) {
	pii val = mp(when[x], x);
	x+=base;
	while(x) {
		tree_max[x] = max(tree_max[x], val);	
		x/=2;
	}
}
pii find_max(int l, int r) {
	if(l>r) {
		return max(find_max(l, n-1), find_max(0, r));
	}
	l+=base, r+=base;
	pii res = tree_max[l];
	if(l!=r) res = max(res, tree_max[r]);
	while(l/2 != r/2) {
		if(l%2==0) res = max(res, tree_max[l+1]);
		if(r%2==1) res = max(res, tree_max[r-1]);
		l /= 2;
		r /= 2;
	}
	return res;
}

int tree[2*base+1], push[2*base+1];
void ADD(int id, int val) {
	tree[id] += val;
	push[id] += val;
}
void add(int l, int r, int val, int id=1, int rl=0, int rr=base-1) {
	if(l>r) {
		add(l, n-1, val), add(0, r, val);
		return;
	}
	if(l>rr || r<rl) return;
	if(l<=rl && r>=rr) {
		ADD(id, val);
		return;
	}
	ADD(id*2, push[id]), ADD(id*2+1, push[id]);
	push[id] = 0;
	add(l, r, val, id*2, rl, (rl+rr)/2), add(l, r, val, id*2+1, (rl+rr)/2+1, rr);
	tree[id] = min(tree[id*2], tree[id*2+1]);
}
int find_closest_zero(int l, int r, int id=1, int rl=0, int rr=base-1) {
	if(l>rr || r<rl || tree[id]>0) return -1;
	if(rl==rr) {
		return rl;
	}

	ADD(id*2, push[id]), ADD(id*2+1, push[id]);
	push[id] = 0;

	int rs = find_closest_zero(l, r, id*2+1, (rl+rr)/2+1, rr);
	if(rs!=-1) return rs;
	return find_closest_zero(l, r, id*2, rl, (rl+rr)/2);
}
int clw_dist(int x, int y) {
	return (x<=y)? y-x: n-(x-y);
}

void solve(int x) {
	//cerr<<"solve("<<x<<")\n";
	while(true) {
		int prv = -1;
		if(x>0) {
			prv = find_closest_zero(0, x-1);
		}
		if(x<n-1 && prv==-1) {
			prv = find_closest_zero(x+1, n-1);
		}
		if(prv != -1 && clw_dist(prv, x) < k) {
			//cerr<<"->";
			solve(prv);
		}
		else {
			break;
		}
	}
	when[x] = ++nr;
	ptr[x] = find_max((x+1)%n, (x+k-1)%n).second;
	ptrr[x] = find_max((x-(k-1)+n)%n, (x-1+n)%n).second;

	add((x-(k-1)+n)%n, (x-1+n)%n, -1);
	add(x, x, n);
	upd(x);
}

void prep_jumps();
void init(int _k, vector<int> _r) {
	k = _k, R = _r, n = R.size();	

	for(int i=0; i<2*base; ++i) {
		tree_max[i] = mp(-1, -1);
	}

	for(int i=0; i<n; ++i) {
		tree[i+base] = R[i];
	}
	for(int i=base-1; i>=1; --i) {
		tree[i] = min(tree[i*2], tree[i*2+1]);
	}

	while(nr < n) {
		int cur = find_closest_zero(0, n-1);	
		assert(cur != -1);
		solve(cur);
	}
	prep_jumps();
}

const int L = 19;
pii jump[L][MAXN], jumpr[L][MAXN];
void prep_jumps() {
	for(int i=0; i<n; ++i) {
		jump[0][i] = mp(ptr[i], clw_dist(i, ptr[i]));
		jumpr[0][i] = mp(ptrr[i], clw_dist(ptrr[i], i));
	}
	for(int l=1; l<L; ++l) {
		for(int i=0; i<n; ++i) {
			if(jump[l-1][i].st != -1) {
				jump[l][i] = jump[l-1][jump[l-1][i].st];
				jump[l][i].nd += jump[l-1][i].nd;
				jump[l][i].nd = min(n, jump[l][i].nd);
			}
			else {
				jump[l][i] = mp(-1, 1);
			}

			if(jumpr[l-1][i].st != -1) {
				jumpr[l][i] = jumpr[l-1][jumpr[l-1][i].st];
				jumpr[l][i].nd += jumpr[l-1][i].nd;
				jumpr[l][i].nd = min(n, jumpr[l][i].nd);
			}
			else {
				jumpr[l][i] = mp(-1, 1);
			}
		}
	}
}
bool is_bigger(int _x, int y) {
	int x = _x;
	for(int l=L-1; l>=0; --l) {
		if(jump[l][x].st!=-1 && jump[l][x].nd <= clw_dist(x, y)) {
			x = jump[l][x].st;
		}
	}
	if(clw_dist(x, y)<k && when[x] >= when[y]) return true;

	for(int l=L-1; l>=0; --l) {
		if(jumpr[l][x].st!=-1 && jumpr[l][x].nd <= clw_dist(y, x)) {
			x = jumpr[l][x].st;
		}
	}
	x = _x;
	if(clw_dist(y, x)<k  && when[x] >= when[y]) return true;
	return false;
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5740 KB Output is correct
2 Correct 5 ms 5740 KB Output is correct
3 Correct 6 ms 5740 KB Output is correct
4 Correct 4 ms 5740 KB Output is correct
5 Incorrect 4 ms 5740 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 5740 KB Output is correct
2 Correct 4 ms 5740 KB Output is correct
3 Correct 4 ms 5760 KB Output is correct
4 Correct 4 ms 5740 KB Output is correct
5 Correct 5 ms 5868 KB Output is correct
6 Correct 9 ms 6124 KB Output is correct
7 Correct 139 ms 10476 KB Output is correct
8 Correct 6 ms 5868 KB Output is correct
9 Correct 9 ms 6124 KB Output is correct
10 Correct 136 ms 10476 KB Output is correct
11 Correct 108 ms 10476 KB Output is correct
12 Correct 113 ms 10476 KB Output is correct
13 Correct 137 ms 10584 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5740 KB Output is correct
2 Correct 4 ms 5740 KB Output is correct
3 Correct 4 ms 5760 KB Output is correct
4 Correct 4 ms 5740 KB Output is correct
5 Correct 5 ms 5868 KB Output is correct
6 Correct 9 ms 6124 KB Output is correct
7 Correct 139 ms 10476 KB Output is correct
8 Correct 6 ms 5868 KB Output is correct
9 Correct 9 ms 6124 KB Output is correct
10 Correct 136 ms 10476 KB Output is correct
11 Correct 108 ms 10476 KB Output is correct
12 Correct 113 ms 10476 KB Output is correct
13 Correct 137 ms 10584 KB Output is correct
14 Correct 223 ms 15468 KB Output is correct
15 Correct 1537 ms 74468 KB Output is correct
16 Correct 210 ms 15468 KB Output is correct
17 Correct 1522 ms 74476 KB Output is correct
18 Correct 737 ms 80748 KB Output is correct
19 Correct 1000 ms 74604 KB Output is correct
20 Correct 1496 ms 74604 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5740 KB Output is correct
2 Correct 4 ms 5740 KB Output is correct
3 Incorrect 100 ms 9580 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 5740 KB Output is correct
2 Correct 4 ms 5740 KB Output is correct
3 Incorrect 4 ms 5740 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 5740 KB Output is correct
2 Correct 4 ms 5740 KB Output is correct
3 Incorrect 4 ms 5740 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 5740 KB Output is correct
2 Correct 5 ms 5740 KB Output is correct
3 Correct 6 ms 5740 KB Output is correct
4 Correct 4 ms 5740 KB Output is correct
5 Incorrect 4 ms 5740 KB Output isn't correct
6 Halted 0 ms 0 KB -