oj.uz

Submission #300984

# Submission time Handle Problem Language Result Execution time Memory
300984 2020-09-17T15:40:42 Z gs14004 Comparing Plants (IOI20_plants) C++17
30 / 100
 4000 ms 132784 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define rank fuck
using namespace std;
using lint = long long;
using llf = long double;
using pi = pair<lint, lint>;
const int MAXN = 200005;
const int MAXT = 2100005;

int n, rank[MAXN];
lint DL[18][MAXN], DR[18][MAXN];
int L[18][MAXN], R[18][MAXN];
vector<int> lev[MAXN];

struct node{
	int minv;
	int lidx, ridx;
	node(){
		minv = 1e9;
	}
	node(int x, int v){
		lidx = ridx = x;
		minv = v;
	}
	node operator+(const node &n)const{
		node x = *this;
		node y = n;
		if(x.minv < y.minv) return x;
		if(x.minv > y.minv) return y;
		x.lidx = min(x.lidx, y.lidx);
		x.ridx = max(x.ridx, y.ridx);
		return x;
	}
};

struct seg{
	node tree[MAXT];
	int lim;
	void init(int n){
		for(lim = 1; lim <= 3 * n; lim <<= 1);
		for(int i=0; i<3*n; i++) tree[i + lim] = node(i-n, 1e9);
		for(int i=lim-1; i; i--) tree[i] = tree[2*i] + tree[2*i+1];
	}
	void upd(int x, int v){
		node val(x, v);
		x += n + lim;
		tree[x] = val;
		while(x > 1){
			x >>= 1;
			tree[x] = tree[2*x] + tree[2*x+1];
		}
	}
	node query(int s, int e){
		s += lim + n;
		e += lim + n;
		node ret;
		while(s < e){
			if(s%2 == 1) ret = ret + tree[s++];
			if(e%2 == 0) ret = ret + tree[e--];
			s >>= 1;
			e >>= 1;
		}
		if(s == e) ret = ret + tree[s];
		return ret;
	}
}seg;

struct sex{
	int tree[530005], lazy[530005];
	void init(int s, int e, vector<int> &v, int p){
		if(s == e){
			tree[p] = v[s];
			return;
		}
		int m = (s+e)/2;
		init(s, m, v, 2*p);
		init(m+1, e, v, 2*p+1);
		tree[p] = min(tree[2*p], tree[2*p+1]);
	}
	void lazydown(int p){
		for(int i=2*p; i<2*p+2; i++){
			tree[i] += lazy[p];
			lazy[i] += lazy[p];
		}
		lazy[p] = 0;
	}
	void add(int s, int e, int ps, int pe, int p, int v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			tree[p] += v;
			lazy[p] += v;
			return;
		}
		int pm = (ps+pe)/2;
		lazydown(p);
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm+1, pe, 2*p+1, v);
		tree[p] = min(tree[2*p], tree[2*p+1]);
	}
	int query(int s, int e, int ps, int pe, int p){
		if(e < ps || pe < s) return 1e9;
		if(s <= ps && pe <= e) return tree[p];
		int pm = (ps+pe)/2;
		lazydown(p);
		return min(query(s, e, ps, pm, 2*p), query(s, e, pm+1, pe, 2*p+1));
	}
}sex;

void init(int k, std::vector<int> r) {
	n = sz(r);
	int layer = 0;
	set<int> unused;
	for(int i=0; i<n; i++) unused.insert(i);
	sex.init(0, n-1, r, 1);
	auto QUERY = [&](int st, int ed){
		int ret = 1e9;
		if(st < n) ret = min(ret, sex.query(st, min(ed, n - 1), 0, n - 1, 1));
		if(ed >= n) ret = min(ret, sex.query(max(st - n, 0), ed - n, 0, n - 1, 1));
		return ret;
	};
	auto cond = [&](int j){
		if(QUERY(j, j)) return false;
		return QUERY(j + n - (k - 1), j + n - 1) > 0;
	};
	auto ADD = [&](int st, int ed, int x){
		if(st < n) sex.add(st, min(ed, n - 1), 0, n - 1, 1, x);
		if(ed >= n) sex.add(max(st - n, 0), ed - n, 0, n - 1, 1, x);
	};
	vector<int> cur;
	for(int i=0; i<n; i++){
		if(cond(i)) cur.push_back(i);
	}
	while(sz(unused)){
		vector<int> nxt;
		layer++;
		for(auto &j : cur){
			if(unused.find(j) == unused.end()) continue;
			unused.erase(j);
			rank[j] = layer;
			ADD(j, j, k-1);
			ADD(j-k+1+n, j-1+n, -1);
			int p1 = (j - k + 1 + n) % n;
			int p2 = (j + 1) % n;
			for(int i=0; i<k-1; i++){
				if(!QUERY(p1, p1)){
					if(cond(p1)){
						nxt.push_back(p1);
					}
					break;
				}
				p1 = (p1 + 1) % n;
			}
			for(int i=0; i<k-1; i++){
				if(!QUERY(p2, p2)){
					if(cond(p2)){
						nxt.push_back(p2);
					}
					break;
				}
				p2 = (p2 + 1) % n;
			}
		}
		cur = nxt;
	}
	for(int i=0; i<n; i++){
		lev[rank[i]].push_back(i);
	}
	seg.init(n);
	for(int i=layer; i; i--){
		for(auto &j : lev[i]){
			L[0][j] = j;
			auto qr = seg.query(j-k+1, j-1);
			if(qr.minv > 1e8) continue;
			if(qr.lidx < j) L[0][j] = (qr.lidx + n) % n;
			DL[0][j] = (j - L[0][j] + n) % n;
		}
		for(auto &j : lev[i]){
			R[0][j] = j;
			auto qr = seg.query(j+1, j+k-1);
			if(qr.minv > 1e8) continue;
			if(qr.ridx > j) R[0][j] = (qr.ridx + n) % n;
			DR[0][j] = (R[0][j] - j + n) % n;
		}
		for(auto &j : lev[i]){
			seg.upd(j - n, i);
			seg.upd(j    , i);
			seg.upd(j + n, i);
		}
	}
	for(int i=1; i<18; i++){
		for(int j=0; j<n; j++){
			L[i][j] = L[i-1][L[i-1][j]];
			R[i][j] = R[i-1][R[i-1][j]];
			DL[i][j] = DL[i-1][j] + DL[i-1][L[i-1][j]];
			DR[i][j] = DR[i-1][j] + DR[i-1][R[i-1][j]];
		}
	}
}

int compare_plants(int x, int y) {
	if(rank[x] == rank[y]) return 0;
	if(rank[x] > rank[y]) return -compare_plants(y, x);
	lint st = x, ed = x;
	{
		lint dist = 0;
		int p = x;
		for(int i=17; i>=0; i--){
			if(rank[L[i][p]] <= rank[y]){
				dist += DL[i][p];
				p = L[i][p];
			}
		}
		st = x - dist;
	}
	{
		lint dist = 0;
		int p = x;
		for(int i=17; i>=0; i--){
			if(rank[R[i][p]] <= rank[y]){
				dist += DR[i][p];
				p = R[i][p];
			}
		}
		ed = x + dist;
	}
	lint Q = ed - ed % n + y;
	if(Q > ed) Q -= n;
	return Q >= st;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30080 KB Output is correct
2 Correct 18 ms 30208 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 17 ms 30080 KB Output is correct
5 Correct 18 ms 30080 KB Output is correct
6 Correct 103 ms 33016 KB Output is correct
7 Correct 364 ms 43168 KB Output is correct
8 Correct 1432 ms 132784 KB Output is correct
9 Correct 1563 ms 132472 KB Output is correct
10 Correct 1532 ms 131524 KB Output is correct
11 Correct 1442 ms 131216 KB Output is correct
12 Correct 1405 ms 131104 KB Output is correct
13 Correct 1461 ms 130936 KB Output is correct
14 Correct 1353 ms 131016 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 30080 KB Output is correct
2 Correct 18 ms 30080 KB Output is correct
3 Correct 18 ms 30208 KB Output is correct
4 Correct 18 ms 30112 KB Output is correct
5 Correct 22 ms 30208 KB Output is correct
6 Correct 126 ms 30712 KB Output is correct
7 Correct 3308 ms 35608 KB Output is correct
8 Correct 22 ms 30208 KB Output is correct
9 Correct 120 ms 30768 KB Output is correct
10 Correct 3481 ms 35576 KB Output is correct
11 Correct 179 ms 35448 KB Output is correct
12 Correct 3560 ms 35716 KB Output is correct
13 Correct 3658 ms 35604 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 30080 KB Output is correct
2 Correct 18 ms 30080 KB Output is correct
3 Correct 18 ms 30208 KB Output is correct
4 Correct 18 ms 30112 KB Output is correct
5 Correct 22 ms 30208 KB Output is correct
6 Correct 126 ms 30712 KB Output is correct
7 Correct 3308 ms 35608 KB Output is correct
8 Correct 22 ms 30208 KB Output is correct
9 Correct 120 ms 30768 KB Output is correct
10 Correct 3481 ms 35576 KB Output is correct
11 Correct 179 ms 35448 KB Output is correct
12 Correct 3560 ms 35716 KB Output is correct
13 Correct 3658 ms 35604 KB Output is correct
14 Execution timed out 4085 ms 33784 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30208 KB Output is correct
2 Correct 18 ms 30208 KB Output is correct
3 Correct 146 ms 34040 KB Output is correct
4 Correct 1676 ms 132524 KB Output is correct
5 Execution timed out 4104 ms 47736 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 30080 KB Output is correct
2 Correct 19 ms 30208 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 17 ms 30080 KB Output is correct
5 Correct 18 ms 30112 KB Output is correct
6 Correct 20 ms 30208 KB Output is correct
7 Correct 40 ms 30976 KB Output is correct
8 Correct 47 ms 30968 KB Output is correct
9 Correct 41 ms 30968 KB Output is correct
10 Correct 49 ms 30972 KB Output is correct
11 Correct 40 ms 30968 KB Output is correct
12 Correct 40 ms 30968 KB Output is correct
13 Correct 48 ms 30968 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30208 KB Output is correct
2 Correct 18 ms 30080 KB Output is correct
3 Correct 23 ms 30072 KB Output is correct
4 Correct 21 ms 30080 KB Output is correct
5 Correct 55 ms 30588 KB Output is correct
6 Execution timed out 4046 ms 47864 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30080 KB Output is correct
2 Correct 18 ms 30208 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 17 ms 30080 KB Output is correct
5 Correct 18 ms 30080 KB Output is correct
6 Correct 103 ms 33016 KB Output is correct
7 Correct 364 ms 43168 KB Output is correct
8 Correct 1432 ms 132784 KB Output is correct
9 Correct 1563 ms 132472 KB Output is correct
10 Correct 1532 ms 131524 KB Output is correct
11 Correct 1442 ms 131216 KB Output is correct
12 Correct 1405 ms 131104 KB Output is correct
13 Correct 1461 ms 130936 KB Output is correct
14 Correct 1353 ms 131016 KB Output is correct
15 Correct 20 ms 30080 KB Output is correct
16 Correct 18 ms 30080 KB Output is correct
17 Correct 18 ms 30208 KB Output is correct
18 Correct 18 ms 30112 KB Output is correct
19 Correct 22 ms 30208 KB Output is correct
20 Correct 126 ms 30712 KB Output is correct
21 Correct 3308 ms 35608 KB Output is correct
22 Correct 22 ms 30208 KB Output is correct
23 Correct 120 ms 30768 KB Output is correct
24 Correct 3481 ms 35576 KB Output is correct
25 Correct 179 ms 35448 KB Output is correct
26 Correct 3560 ms 35716 KB Output is correct
27 Correct 3658 ms 35604 KB Output is correct
28 Execution timed out 4085 ms 33784 KB Time limit exceeded
29 Halted 0 ms 0 KB -