oj.uz

Submission #300922

# Submission time Handle Problem Language Result Execution time Memory
300922 2020-09-17T15:08:56 Z gs14004 Comparing Plants (IOI20_plants) C++17
11 / 100
 104 ms 33016 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;

void init(int k, std::vector<int> r) {
	n = sz(r);
	if(n > 300) return;
	int layer = 0;
	while(count(rank, rank + n, 0)){
		vector<int> vect;
		for(int j=0; j<n; j++){
			if(r[j] || rank[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) rank[j] = layer;
		for(auto &j : vect){
			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 17 ms 30176 KB Output is correct
3 Correct 18 ms 30208 KB Output is correct
4 Correct 18 ms 30112 KB Output is correct
5 Correct 19 ms 30080 KB Output is correct
6 Correct 104 ms 33016 KB Output is correct
7 Incorrect 98 ms 32632 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
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 17 ms 30080 KB Output is correct
5 Correct 21 ms 30336 KB Output is correct
6 Incorrect 19 ms 29696 KB Output isn't correct
7 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 18 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 21 ms 30336 KB Output is correct
6 Incorrect 19 ms 29696 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30064 KB Output is correct
2 Correct 17 ms 30080 KB Output is correct
3 Incorrect 86 ms 32504 KB Output isn't correct
4 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 30080 KB Output is correct
4 Correct 19 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 40 ms 30848 KB Output is correct
8 Correct 43 ms 30968 KB Output is correct
9 Correct 41 ms 30840 KB Output is correct
10 Correct 42 ms 30968 KB Output is correct
11 Correct 42 ms 30840 KB Output is correct
12 Correct 40 ms 30864 KB Output is correct
13 Correct 44 ms 30968 KB Output is correct

Subtask #6
0 / 15.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 Correct 18 ms 30080 KB Output is correct
5 Incorrect 18 ms 29696 KB Output isn't correct
6 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 17 ms 30176 KB Output is correct
3 Correct 18 ms 30208 KB Output is correct
4 Correct 18 ms 30112 KB Output is correct
5 Correct 19 ms 30080 KB Output is correct
6 Correct 104 ms 33016 KB Output is correct
7 Incorrect 98 ms 32632 KB Output isn't correct
8 Halted 0 ms 0 KB -