oj.uz

Submission #300959

# Submission time Handle Problem Language Result Execution time Memory
300959 2020-09-17T15:30:28 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[MAXT], lazy[MAXT];
	void init(int s, int e, vector<int> &v, int p){
		if(s == e){
			tree[p] = v[s % sz(v)];
			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, 2*n-1, r, 1);
	auto cond = [&](int j){
		if(r[j]) return false;
		for(int x=1; x<=k-1; x++){
			if(r[(j-x+n)%n] == 0) return false;
		}
		return true;
	};
	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;
			r[j] = k - 1;
			for(int x=1; x<=k-1; x++){
				r[(j-x+n)%n]--;
			}
			int p1 = (j - k + 1 + n) % n;
			int p2 = (j + 1) % n;
			for(int i=0; i<k-1; i++){
				if(!r[p1]){
					if(cond(p1)){
						nxt.push_back(p1);
					}
					break;
				}
				p1 = (p1 + 1) % n;
			}
			for(int i=0; i<k-1; i++){
				if(!r[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 17 ms 30080 KB Output is correct
2 Correct 18 ms 30080 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 18 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 300 ms 43128 KB Output is correct
8 Correct 910 ms 132784 KB Output is correct
9 Correct 967 ms 132600 KB Output is correct
10 Correct 955 ms 131568 KB Output is correct
11 Correct 950 ms 131064 KB Output is correct
12 Correct 932 ms 130936 KB Output is correct
13 Correct 942 ms 131064 KB Output is correct
14 Correct 989 ms 131064 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30080 KB Output is correct
2 Correct 19 ms 30080 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 18 ms 30068 KB Output is correct
5 Correct 20 ms 30208 KB Output is correct
6 Correct 40 ms 30720 KB Output is correct
7 Correct 651 ms 35700 KB Output is correct
8 Correct 20 ms 30208 KB Output is correct
9 Correct 41 ms 30712 KB Output is correct
10 Correct 633 ms 35704 KB Output is correct
11 Correct 334 ms 35704 KB Output is correct
12 Correct 463 ms 35832 KB Output is correct
13 Correct 790 ms 35704 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30080 KB Output is correct
2 Correct 19 ms 30080 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 18 ms 30068 KB Output is correct
5 Correct 20 ms 30208 KB Output is correct
6 Correct 40 ms 30720 KB Output is correct
7 Correct 651 ms 35700 KB Output is correct
8 Correct 20 ms 30208 KB Output is correct
9 Correct 41 ms 30712 KB Output is correct
10 Correct 633 ms 35704 KB Output is correct
11 Correct 334 ms 35704 KB Output is correct
12 Correct 463 ms 35832 KB Output is correct
13 Correct 790 ms 35704 KB Output is correct
14 Execution timed out 4059 ms 33660 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 30080 KB Output is correct
2 Correct 17 ms 30080 KB Output is correct
3 Correct 162 ms 34040 KB Output is correct
4 Correct 936 ms 132468 KB Output is correct
5 Correct 1399 ms 132600 KB Output is correct
6 Execution timed out 4072 ms 47988 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30112 KB Output is correct
2 Correct 19 ms 30080 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 17 ms 30080 KB Output is correct
5 Correct 23 ms 30592 KB Output is correct
6 Correct 1293 ms 132440 KB Output is correct
7 Execution timed out 4067 ms 47992 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 30080 KB Output is correct
2 Correct 18 ms 30080 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 18 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 300 ms 43128 KB Output is correct
8 Correct 910 ms 132784 KB Output is correct
9 Correct 967 ms 132600 KB Output is correct
10 Correct 955 ms 131568 KB Output is correct
11 Correct 950 ms 131064 KB Output is correct
12 Correct 932 ms 130936 KB Output is correct
13 Correct 942 ms 131064 KB Output is correct
14 Correct 989 ms 131064 KB Output is correct
15 Correct 18 ms 30080 KB Output is correct
16 Correct 19 ms 30080 KB Output is correct
17 Correct 18 ms 30080 KB Output is correct
18 Correct 18 ms 30068 KB Output is correct
19 Correct 20 ms 30208 KB Output is correct
20 Correct 40 ms 30720 KB Output is correct
21 Correct 651 ms 35700 KB Output is correct
22 Correct 20 ms 30208 KB Output is correct
23 Correct 41 ms 30712 KB Output is correct
24 Correct 633 ms 35704 KB Output is correct
25 Correct 334 ms 35704 KB Output is correct
26 Correct 463 ms 35832 KB Output is correct
27 Correct 790 ms 35704 KB Output is correct
28 Execution timed out 4059 ms 33660 KB Time limit exceeded
29 Halted 0 ms 0 KB -