Submission #589764

#	Time	Username	Problem	Language	Result	Execution time	Memory
589764		Lucpp	Comparing Plants (IOI20_plants)	C++17	100 / 100	1809 ms	97056 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
const int LOG = 18;
int n, k, cap;
vector<vector<int>> jumpL, jumpR;
vector<int> h;

struct Data{
	int m = INF, l, r, ind = -1;
};
Data combine(Data a, Data b){
	Data d;
	d.m = min(a.m, b.m);
	if(d.m == a.m) d.l = a.l;
	else d.l = b.l;
	if(d.m == b.m) d.r = b.r;
	else d.r = a.r;
	if(d.m == a.m && a.ind != -1) d.ind = a.ind;
	if(d.m == b.m && b.ind != -1) d.ind = b.ind;
	if(d.m == a.m && d.m == b.m && b.l-a.r >= k) d.ind = b.l;
	return d;
}
vector<Data> S;
vector<int> O;
vector<bool> lazy;
void build(vector<int> v){
	for(cap = 1; cap < (int)v.size(); cap *= 2);
	S.resize(2*cap);
	O.resize(2*cap);
	lazy.resize(2*cap);
	for(int i = 0; i < (int)v.size(); i++) S[i+cap] = Data{v[i], i+1, i+1};
	for(int i = cap-1; i > 0; i--) S[i] = combine(S[2*i], S[2*i+1]);
}
void apply(int v, int i){
	lazy[i] = true;
	O[i] += v;
	S[i].m += v;
}
void push(int i){
	if(lazy[i]){
		apply(O[i], 2*i);
		apply(O[i], 2*i+1);
		O[i] = 0;
		lazy[i] = false;
	}
}
void upd(int p, int v, int a, int b, int i){
	if(a == b) S[i] = {v, p, p, -1};
	else{
		push(i);
		int m = (a+b)/2;
		if(p <= m) upd(p, v, a, m, 2*i);
		else upd(p, v, m+1, b, 2*i+1);
		S[i] = combine(S[2*i], S[2*i+1]);
	}
}
void apply(int l, int r, int v, int a, int b, int i){
	if(l <= a && b <= r) apply(v, i);
	else if(b < l || r < a) return;
	else{
		push(i);
		int m = (a+b)/2;
		apply(l, r, v, a, m, 2*i);
		apply(l, r, v, m+1, b, 2*i+1);
		S[i] = combine(S[2*i], S[2*i+1]);
	}
}

vector<pair<int, int>> S2;
void build2(){
	S2.resize(2*cap, {INF, 0});
	for(int i = cap; i < 2*cap; i++) S2[i].second = i-cap;
}
void upd2(int i, int v){
	i += cap;
	S2[i].first = v;
	while(i > 1){
		i /= 2;
		S2[i] = min(S2[2*i], S2[2*i+1]);
	}
}
pair<int, int> qry2(int l, int r, int a, int b, int i){
	if(l <= a && b <= r) return S2[i];
	if(b < l || r < a) return {INF, 0};
	int m = (a+b)/2;
	return min(qry2(l, r, a, m, 2*i), qry2(l, r, m+1, b, 2*i+1));
}


bool findR(int a, int b){
	for(int i = LOG-1; i >= 0; i--){
		if(jumpR[i][a] == -1) continue;
		if(jumpR[i][a] <= b) a = jumpR[i][a];
	}
	return b-a<k && h[a] <= h[b];
}
bool findL(int a, int b){
	for(int i = LOG-1; i >= 0; i--){
		if(jumpL[i][a] == -1) continue;
		if(jumpL[i][a] >= b) a = jumpL[i][a];
	}
	return a-b<k && h[a] <= h[b];
}

void init(int K, vector<int> r) {
	k = K;
	n = (int)r.size();
	h.resize(2*n);
	r.resize(2*n);
	jumpL.assign(LOG, vector<int>(2*n, -1));
	jumpR.assign(LOG, vector<int>(2*n, -1));
	for(int i = 0; i < n; i++) r[i+n] = r[i];
	build(r);
	build2();
	for(int it = 0; it < n; it++){
		assert(S[1].m == 0);
		assert(S[1].ind != -1);
		int i = S[1].ind;
		i = (i-1)%n;
		h[i] = h[i+n] = n-it;
		upd2(i, h[i]);
		upd2(i+n, h[i]);

		auto p = qry2(i+2, i+k, 1, cap, 1);
		if(p.first != INF) jumpR[0][i] = p.second;
		p = qry2(i+n+2, i+n+k, 1, cap, 1);
		if(p.first != INF) jumpR[0][i+n] = p.second;
		p = qry2(i-k+2, i, 1, cap, 1);
		if(p.first != INF) jumpL[0][i] = p.second;
		p = qry2(i+n-k+2, i+n, 1, cap, 1);
		if(p.first != INF) jumpL[0][i+n] = p.second;

		upd(i+1, INF, 1, cap, 1);
		upd(i+n+1, INF, 1, cap, 1);
		apply(max(0, i-k+1)+1, i, -1, 1, cap, 1);
		apply(i+n-k+2, i+n, -1, 1, cap, 1);
		apply(i+2*n-k+2, 2*n, -1, 1, cap, 1);

	}
	for(int i = 1; i < LOG; i++){
		for(int j = 0; j < 2*n; j++){
			if(jumpR[i-1][j] != -1) jumpR[i][j] = jumpR[i-1][jumpR[i-1][j]];
			if(jumpL[i-1][j] != -1) jumpL[i][j] = jumpL[i-1][jumpL[i-1][j]];
		}
	}
	
}

int compare_plants(int x, int y) {
	if(h[x] < h[y]){
		if(findR(x, y) || findL(x+n, y)) return -1;
		else return 0;
	}
	else{
		if(findR(y, x+n) || findL(y, x)) return 1;
		else return 0;
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25