oj.uz

Submission #373417

# Submission time Handle Problem Language Result Execution time Memory
373417 2021-03-04T14:05:13 Z pit4h Comparing Plants (IOI20_plants) C++14
25 / 100
 4000 ms 21132 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;
	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 6 ms 5484 KB Output is correct
2 Correct 4 ms 5484 KB Output is correct
3 Correct 5 ms 5484 KB Output is correct
4 Correct 4 ms 5484 KB Output is correct
5 Correct 4 ms 5484 KB Output is correct
6 Correct 71 ms 9452 KB Output is correct
7 Correct 196 ms 10860 KB Output is correct
8 Correct 372 ms 16748 KB Output is correct
9 Correct 460 ms 17132 KB Output is correct
10 Correct 1221 ms 17132 KB Output is correct
11 Execution timed out 4011 ms 19124 KB Time limit exceeded
12 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 5 ms 5484 KB Output is correct
5 Correct 6 ms 5484 KB Output is correct
6 Correct 8 ms 5612 KB Output is correct
7 Correct 82 ms 8556 KB Output is correct
8 Correct 6 ms 5612 KB Output is correct
9 Correct 8 ms 5612 KB Output is correct
10 Correct 83 ms 8556 KB Output is correct
11 Correct 576 ms 8684 KB Output is correct
12 Correct 185 ms 8684 KB Output is correct
13 Correct 81 ms 8684 KB Output is correct

Subtask #3
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 5 ms 5484 KB Output is correct
5 Correct 6 ms 5484 KB Output is correct
6 Correct 8 ms 5612 KB Output is correct
7 Correct 82 ms 8556 KB Output is correct
8 Correct 6 ms 5612 KB Output is correct
9 Correct 8 ms 5612 KB Output is correct
10 Correct 83 ms 8556 KB Output is correct
11 Correct 576 ms 8684 KB Output is correct
12 Correct 185 ms 8684 KB Output is correct
13 Correct 81 ms 8684 KB Output is correct
14 Correct 135 ms 9068 KB Output is correct
15 Correct 929 ms 14956 KB Output is correct
16 Correct 135 ms 9068 KB Output is correct
17 Correct 897 ms 15084 KB Output is correct
18 Execution timed out 4021 ms 21132 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
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 284 ms 8428 KB Output is correct
4 Execution timed out 4080 ms 18064 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.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 4 ms 5484 KB Output is correct
6 Correct 7 ms 5612 KB Output is correct
7 Correct 22 ms 6508 KB Output is correct
8 Correct 19 ms 6508 KB Output is correct
9 Correct 27 ms 6508 KB Output is correct
10 Correct 20 ms 6508 KB Output is correct
11 Correct 24 ms 6508 KB Output is correct
12 Correct 23 ms 6508 KB Output is correct
13 Correct 19 ms 6508 KB Output is correct

Subtask #6
0 / 15.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 Correct 4 ms 5484 KB Output is correct
4 Correct 4 ms 5484 KB Output is correct
5 Correct 9 ms 5612 KB Output is correct
6 Correct 795 ms 17260 KB Output is correct
7 Correct 1160 ms 17388 KB Output is correct
8 Correct 836 ms 17644 KB Output is correct
9 Correct 878 ms 17772 KB Output is correct
10 Execution timed out 4070 ms 18660 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5484 KB Output is correct
2 Correct 4 ms 5484 KB Output is correct
3 Correct 5 ms 5484 KB Output is correct
4 Correct 4 ms 5484 KB Output is correct
5 Correct 4 ms 5484 KB Output is correct
6 Correct 71 ms 9452 KB Output is correct
7 Correct 196 ms 10860 KB Output is correct
8 Correct 372 ms 16748 KB Output is correct
9 Correct 460 ms 17132 KB Output is correct
10 Correct 1221 ms 17132 KB Output is correct
11 Execution timed out 4011 ms 19124 KB Time limit exceeded
12 Halted 0 ms 0 KB -