oj.uz

Submission #301012

# Submission time Handle Problem Language Result Execution time Memory
301012 2020-09-17T15:51:45 Z gs14004 Comparing Plants (IOI20_plants) C++17
5 / 100
 4000 ms 132728 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 -1;
		int l = 0, r = k - 1;
		while(l != r){
			int m = (l + r) / 2;
			if(!QUERY(s, s + l)) r = m;
			else l = m + 1;
		}
		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 && cond(pos1)) nxt.push_back(pos1);
			if(~pos2 && 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 17 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 18 ms 30208 KB Output is correct
6 Correct 107 ms 32996 KB Output is correct
7 Correct 310 ms 43128 KB Output is correct
8 Correct 1369 ms 132728 KB Output is correct
9 Correct 1471 ms 132600 KB Output is correct
10 Correct 1431 ms 131704 KB Output is correct
11 Correct 1372 ms 131064 KB Output is correct
12 Correct 1334 ms 130936 KB Output is correct
13 Correct 1397 ms 131192 KB Output is correct
14 Correct 1335 ms 131064 KB Output is correct

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

Subtask #6
0 / 15.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 18 ms 30080 KB Output is correct
5 Execution timed out 4059 ms 29824 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 17 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 18 ms 30208 KB Output is correct
6 Correct 107 ms 32996 KB Output is correct
7 Correct 310 ms 43128 KB Output is correct
8 Correct 1369 ms 132728 KB Output is correct
9 Correct 1471 ms 132600 KB Output is correct
10 Correct 1431 ms 131704 KB Output is correct
11 Correct 1372 ms 131064 KB Output is correct
12 Correct 1334 ms 130936 KB Output is correct
13 Correct 1397 ms 131192 KB Output is correct
14 Correct 1335 ms 131064 KB Output is correct
15 Correct 18 ms 30080 KB Output is correct
16 Correct 17 ms 30080 KB Output is correct
17 Correct 18 ms 30080 KB Output is correct
18 Correct 18 ms 30080 KB Output is correct
19 Execution timed out 4065 ms 29696 KB Time limit exceeded
20 Halted 0 ms 0 KB -