oj.uz

Submission #300998

# Submission time Handle Problem Language Result Execution time Memory
300998 2020-09-17T15:47:08 Z gs14004 Comparing Plants (IOI20_plants) C++17
5 / 100
 4000 ms 132908 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));
	}
	int find_first(int s, int e, int ps, int pe, int p){

	}
}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);
	};
	auto FIND_FIRST = [&](int s, int k){
		if(QUERY(s, s + k - 1)) return (s + k) % n;
		int l = 0, r = k - 1;
		while(l != r){
			int m = (l + r) / 2;
			if(QUERY(s, s + l)) l = m + 1;
			else r = m;
		}
		return (s + l) % n;
	};
	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;
			int pos1 = FIND_FIRST(p1, k - 1);
			int pos2 = FIND_FIRST(p2, k - 1);
			if((pos1 - p1 + n) % n < k - 1 && cond(pos1)) nxt.push_back(pos1);
			if((pos2 - p2 + n) % n < k - 1 && cond(pos2)) nxt.push_back(pos2);
		}
		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;
}

Compilation message

plants.cpp: In member function 'int sex::find_first(int, int, int, int, int)':
plants.cpp:112:2: warning: no return statement in function returning non-void [-Wreturn-type]
  112 |  }
      |  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30208 KB Output is correct
2 Correct 18 ms 30080 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 19 ms 30208 KB Output is correct
5 Correct 18 ms 30080 KB Output is correct
6 Correct 104 ms 33016 KB Output is correct
7 Correct 349 ms 43060 KB Output is correct
8 Correct 1367 ms 132908 KB Output is correct
9 Correct 1473 ms 132472 KB Output is correct
10 Correct 1437 ms 131704 KB Output is correct
11 Correct 1378 ms 131192 KB Output is correct
12 Correct 1371 ms 131064 KB Output is correct
13 Correct 1422 ms 131320 KB Output is correct
14 Correct 1341 ms 130936 KB Output is correct

Subtask #2
0 / 14.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 19 ms 30080 KB Output is correct
4 Correct 17 ms 30080 KB Output is correct
5 Execution timed out 4043 ms 29696 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 19 ms 30080 KB Output is correct
4 Correct 17 ms 30080 KB Output is correct
5 Execution timed out 4043 ms 29696 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30080 KB Output is correct
2 Execution timed out 4046 ms 29696 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
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 17 ms 30080 KB Output is correct
5 Correct 18 ms 30208 KB Output is correct
6 Execution timed out 4058 ms 29688 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 18 ms 30080 KB Output is correct
4 Correct 18 ms 30080 KB Output is correct
5 Execution timed out 4078 ms 29816 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30208 KB Output is correct
2 Correct 18 ms 30080 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 19 ms 30208 KB Output is correct
5 Correct 18 ms 30080 KB Output is correct
6 Correct 104 ms 33016 KB Output is correct
7 Correct 349 ms 43060 KB Output is correct
8 Correct 1367 ms 132908 KB Output is correct
9 Correct 1473 ms 132472 KB Output is correct
10 Correct 1437 ms 131704 KB Output is correct
11 Correct 1378 ms 131192 KB Output is correct
12 Correct 1371 ms 131064 KB Output is correct
13 Correct 1422 ms 131320 KB Output is correct
14 Correct 1341 ms 130936 KB Output is correct
15 Correct 18 ms 30208 KB Output is correct
16 Correct 18 ms 30208 KB Output is correct
17 Correct 19 ms 30080 KB Output is correct
18 Correct 17 ms 30080 KB Output is correct
19 Execution timed out 4043 ms 29696 KB Time limit exceeded
20 Halted 0 ms 0 KB -