oj.uz

Submission #301018

# Submission time Handle Problem Language Result Execution time Memory
301018 2020-09-17T15:53:32 Z gs14004 Comparing Plants (IOI20_plants) C++17
30 / 100
 4000 ms 132788 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 + m)) 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 19 ms 30080 KB Output is correct
2 Correct 20 ms 30072 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 21 ms 30208 KB Output is correct
5 Correct 19 ms 30208 KB Output is correct
6 Correct 105 ms 33016 KB Output is correct
7 Correct 377 ms 43132 KB Output is correct
8 Correct 1409 ms 132788 KB Output is correct
9 Correct 1544 ms 132468 KB Output is correct
10 Correct 1495 ms 131580 KB Output is correct
11 Correct 1462 ms 131064 KB Output is correct
12 Correct 1425 ms 130932 KB Output is correct
13 Correct 1430 ms 131064 KB Output is correct
14 Correct 1341 ms 131144 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 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 30208 KB Output is correct
6 Correct 29 ms 30712 KB Output is correct
7 Correct 227 ms 35576 KB Output is correct
8 Correct 20 ms 30208 KB Output is correct
9 Correct 27 ms 30720 KB Output is correct
10 Correct 225 ms 35576 KB Output is correct
11 Correct 195 ms 35448 KB Output is correct
12 Correct 188 ms 35832 KB Output is correct
13 Correct 235 ms 35576 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 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 30208 KB Output is correct
6 Correct 29 ms 30712 KB Output is correct
7 Correct 227 ms 35576 KB Output is correct
8 Correct 20 ms 30208 KB Output is correct
9 Correct 27 ms 30720 KB Output is correct
10 Correct 225 ms 35576 KB Output is correct
11 Correct 195 ms 35448 KB Output is correct
12 Correct 188 ms 35832 KB Output is correct
13 Correct 235 ms 35576 KB Output is correct
14 Correct 533 ms 43272 KB Output is correct
15 Execution timed out 4103 ms 132508 KB Time limit exceeded
16 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 Correct 19 ms 30080 KB Output is correct
3 Correct 149 ms 34040 KB Output is correct
4 Correct 1519 ms 132424 KB Output is correct
5 Correct 2005 ms 132744 KB Output is correct
6 Correct 3124 ms 132556 KB Output is correct
7 Correct 3798 ms 132472 KB Output is correct
8 Execution timed out 4077 ms 132472 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.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 30208 KB Output is correct
4 Correct 18 ms 30080 KB Output is correct
5 Correct 18 ms 30208 KB Output is correct
6 Correct 20 ms 30208 KB Output is correct
7 Correct 39 ms 30968 KB Output is correct
8 Correct 42 ms 30968 KB Output is correct
9 Correct 42 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 45 ms 30968 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 30080 KB Output is correct
2 Correct 17 ms 30180 KB Output is correct
3 Correct 17 ms 30080 KB Output is correct
4 Correct 18 ms 30208 KB Output is correct
5 Correct 25 ms 30592 KB Output is correct
6 Correct 2056 ms 132764 KB Output is correct
7 Correct 2785 ms 132600 KB Output is correct
8 Correct 3457 ms 132472 KB Output is correct
9 Execution timed out 4062 ms 101324 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30080 KB Output is correct
2 Correct 20 ms 30072 KB Output is correct
3 Correct 18 ms 30080 KB Output is correct
4 Correct 21 ms 30208 KB Output is correct
5 Correct 19 ms 30208 KB Output is correct
6 Correct 105 ms 33016 KB Output is correct
7 Correct 377 ms 43132 KB Output is correct
8 Correct 1409 ms 132788 KB Output is correct
9 Correct 1544 ms 132468 KB Output is correct
10 Correct 1495 ms 131580 KB Output is correct
11 Correct 1462 ms 131064 KB Output is correct
12 Correct 1425 ms 130932 KB Output is correct
13 Correct 1430 ms 131064 KB Output is correct
14 Correct 1341 ms 131144 KB Output is correct
15 Correct 18 ms 30080 KB Output is correct
16 Correct 18 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 Correct 19 ms 30208 KB Output is correct
20 Correct 29 ms 30712 KB Output is correct
21 Correct 227 ms 35576 KB Output is correct
22 Correct 20 ms 30208 KB Output is correct
23 Correct 27 ms 30720 KB Output is correct
24 Correct 225 ms 35576 KB Output is correct
25 Correct 195 ms 35448 KB Output is correct
26 Correct 188 ms 35832 KB Output is correct
27 Correct 235 ms 35576 KB Output is correct
28 Correct 533 ms 43272 KB Output is correct
29 Execution timed out 4103 ms 132508 KB Time limit exceeded
30 Halted 0 ms 0 KB -