oj.uz

Submission #300958

# Submission time Handle Problem Language Result Execution time Memory
300958 2020-09-17T15:29:04 Z gs14004 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 35832 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){
			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;
			}
		}
		sort(all(nxt));
		nxt.resize(unique(all(nxt)) - nxt.begin());
		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
0 / 5.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 Incorrect 18 ms 30080 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 19 ms 30080 KB Output is correct
2 Correct 18 ms 30080 KB Output is correct
3 Correct 22 ms 30080 KB Output is correct
4 Correct 18 ms 30080 KB Output is correct
5 Correct 20 ms 30184 KB Output is correct
6 Correct 50 ms 30712 KB Output is correct
7 Correct 719 ms 35632 KB Output is correct
8 Correct 25 ms 30208 KB Output is correct
9 Correct 41 ms 30712 KB Output is correct
10 Correct 630 ms 35824 KB Output is correct
11 Correct 328 ms 35448 KB Output is correct
12 Correct 465 ms 35832 KB Output is correct
13 Correct 792 ms 35704 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30080 KB Output is correct
2 Correct 18 ms 30080 KB Output is correct
3 Correct 22 ms 30080 KB Output is correct
4 Correct 18 ms 30080 KB Output is correct
5 Correct 20 ms 30184 KB Output is correct
6 Correct 50 ms 30712 KB Output is correct
7 Correct 719 ms 35632 KB Output is correct
8 Correct 25 ms 30208 KB Output is correct
9 Correct 41 ms 30712 KB Output is correct
10 Correct 630 ms 35824 KB Output is correct
11 Correct 328 ms 35448 KB Output is correct
12 Correct 465 ms 35832 KB Output is correct
13 Correct 792 ms 35704 KB Output is correct
14 Execution timed out 4083 ms 33784 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 30080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30204 KB Output is correct
2 Correct 17 ms 30080 KB Output is correct
3 Correct 18 ms 30208 KB Output is correct
4 Correct 18 ms 30080 KB Output is correct
5 Incorrect 18 ms 30080 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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