oj.uz

Submission #300945

# Submission time Handle Problem Language Result Execution time Memory
300945 2020-09-17T15:24:11 Z gs14004 Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 132596 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);
	while(sz(unused)){
		vector<int> vect;
		for(auto &j : unused){
			if(r[j]) continue;
			bool claim = true;
			for(int x=1; x<=k-1; x++){
				if(r[(j-x+n)%n] == 0) claim = false;
			}
			if(claim) vect.push_back(j);
		}
		layer++;
		for(auto &j : vect){
			unused.erase(j);
			rank[j] = layer;
			r[j] = k - 1;
			for(int x=1; x<=k-1; x++){
				r[(j-x+n)%n]--;
			}
		}
	}
	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 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 109 ms 33008 KB Output is correct
7 Correct 342 ms 43160 KB Output is correct
8 Correct 976 ms 132596 KB Output is correct
9 Correct 1321 ms 131836 KB Output is correct
10 Correct 3518 ms 130468 KB Output is correct
11 Execution timed out 4067 ms 47344 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30080 KB Output is correct
2 Correct 19 ms 30180 KB Output is correct
3 Correct 23 ms 30080 KB Output is correct
4 Correct 18 ms 30080 KB Output is correct
5 Correct 21 ms 30208 KB Output is correct
6 Correct 40 ms 30708 KB Output is correct
7 Correct 634 ms 35580 KB Output is correct
8 Correct 22 ms 30248 KB Output is correct
9 Correct 39 ms 30712 KB Output is correct
10 Correct 642 ms 35572 KB Output is correct
11 Execution timed out 4032 ms 32492 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30080 KB Output is correct
2 Correct 19 ms 30180 KB Output is correct
3 Correct 23 ms 30080 KB Output is correct
4 Correct 18 ms 30080 KB Output is correct
5 Correct 21 ms 30208 KB Output is correct
6 Correct 40 ms 30708 KB Output is correct
7 Correct 634 ms 35580 KB Output is correct
8 Correct 22 ms 30248 KB Output is correct
9 Correct 39 ms 30712 KB Output is correct
10 Correct 642 ms 35572 KB Output is correct
11 Execution timed out 4032 ms 32492 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30184 KB Output is correct
2 Correct 21 ms 30080 KB Output is correct
3 Correct 170 ms 34040 KB Output is correct
4 Execution timed out 4067 ms 47172 KB Time limit exceeded
5 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 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 19 ms 30080 KB Output is correct
6 Correct 20 ms 30192 KB Output is correct
7 Correct 40 ms 30840 KB Output is correct
8 Correct 43 ms 30968 KB Output is correct
9 Correct 41 ms 30968 KB Output is correct
10 Correct 43 ms 30968 KB Output is correct
11 Correct 40 ms 30968 KB Output is correct
12 Correct 41 ms 30968 KB Output is correct
13 Correct 44 ms 31000 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 30080 KB Output is correct
2 Correct 17 ms 30080 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 18 ms 30112 KB Output is correct
5 Correct 23 ms 30592 KB Output is correct
6 Correct 1829 ms 131328 KB Output is correct
7 Execution timed out 4073 ms 47864 KB Time limit exceeded
8 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 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 109 ms 33008 KB Output is correct
7 Correct 342 ms 43160 KB Output is correct
8 Correct 976 ms 132596 KB Output is correct
9 Correct 1321 ms 131836 KB Output is correct
10 Correct 3518 ms 130468 KB Output is correct
11 Execution timed out 4067 ms 47344 KB Time limit exceeded
12 Halted 0 ms 0 KB -