oj.uz

Submission #373416

# Submission time Handle Problem Language Result Execution time Memory
373416 2021-03-04T14:04:13 Z pit4h Comparing Plants (IOI20_plants) C++14
44 / 100
 938 ms 30340 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 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);
	}
}

bool is_bigger(int _x, int y) {
	int x = _x;
	return when[x] > when[y];
	while(x!=-1 && clw_dist(x, y)>=k) {
		x = ptr[x];	
	}
	if(x!=-1 && when[x] >= when[y]) return true;

	x = _x;
	while(x != -1 && clw_dist(y, x)>=k) {
		x = ptrr[x];
	}
	if(x!=-1 && 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 5484 KB Output is correct
2 Correct 4 ms 5484 KB Output is correct
3 Correct 5 ms 5612 KB Output is correct
4 Incorrect 4 ms 5484 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5484 KB Output is correct
2 Correct 4 ms 5484 KB Output is correct
3 Correct 4 ms 5484 KB Output is correct
4 Correct 4 ms 5484 KB Output is correct
5 Correct 5 ms 5484 KB Output is correct
6 Correct 8 ms 5612 KB Output is correct
7 Correct 105 ms 9604 KB Output is correct
8 Correct 7 ms 5612 KB Output is correct
9 Correct 8 ms 5612 KB Output is correct
10 Correct 83 ms 10476 KB Output is correct
11 Correct 90 ms 10604 KB Output is correct
12 Correct 90 ms 10604 KB Output is correct
13 Correct 86 ms 10468 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5484 KB Output is correct
2 Correct 4 ms 5484 KB Output is correct
3 Correct 4 ms 5484 KB Output is correct
4 Correct 4 ms 5484 KB Output is correct
5 Correct 5 ms 5484 KB Output is correct
6 Correct 8 ms 5612 KB Output is correct
7 Correct 105 ms 9604 KB Output is correct
8 Correct 7 ms 5612 KB Output is correct
9 Correct 8 ms 5612 KB Output is correct
10 Correct 83 ms 10476 KB Output is correct
11 Correct 90 ms 10604 KB Output is correct
12 Correct 90 ms 10604 KB Output is correct
13 Correct 86 ms 10468 KB Output is correct
14 Correct 137 ms 11372 KB Output is correct
15 Correct 938 ms 18796 KB Output is correct
16 Correct 145 ms 11244 KB Output is correct
17 Correct 925 ms 18796 KB Output is correct
18 Correct 540 ms 24664 KB Output is correct
19 Correct 583 ms 18660 KB Output is correct
20 Correct 861 ms 18796 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5484 KB Output is correct
2 Correct 4 ms 5484 KB Output is correct
3 Correct 72 ms 9580 KB Output is correct
4 Correct 408 ms 21100 KB Output is correct
5 Correct 467 ms 18796 KB Output is correct
6 Correct 690 ms 18284 KB Output is correct
7 Correct 784 ms 18528 KB Output is correct
8 Correct 901 ms 18644 KB Output is correct
9 Correct 418 ms 19564 KB Output is correct
10 Correct 416 ms 19268 KB Output is correct
11 Correct 376 ms 30340 KB Output is correct
12 Correct 457 ms 18028 KB Output is correct
13 Correct 520 ms 26732 KB Output is correct

Subtask #5
0 / 11.0

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