Submission #1050045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050045		fuad27	Comparing Plants (IOI20_plants)	C++17	25 / 100	4053 ms	25824 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;

struct lazy_segtree {
	vector<pair<int,int>> T;
	vector<int> lz;
	int n;
	void build(vector<int> &a, int tl, int tr, int v) {
		if(tl == tr) {
			T[v] = {a[tl], tl};
			return;
		}
		int tm = (tl+tr)/2;
		build(a, tl, tm, 2*v);
		build(a, tm+1, tr, 2*v+1);
		T[v] = min(T[2*v], T[2*v+1]);

	}
	lazy_segtree(vector<int> &a) {
		n=a.size();	
		T.resize(4*n);
		lz.resize(4*n);
		build(a, 0, n-1, 1);
	}
	void push(int v){
		lz[2*v] += lz[v];
		lz[2*v+1] += lz[v];
		T[2*v].first += lz[v];
		T[2*v+1].first += lz[v];
		lz[v] = 0;
	}
	void update(int l, int r, int add, int tl, int tr, int v) {
		if(r < tl or tr < l)return;
		if(l <= tl and tr<=r) {
			lz[v]+=add;
			T[v].first+=add;
			return;
		}
		push(v);
		int tm=(tl+tr)/2;
		update(l, r, add, tl, tm, 2*v);
		update(l, r, add, tm+1, tr, 2*v+1);
		T[v] = min(T[2*v], T[2*v+1]);
	}
	pair<int,int> query(int l, int r, int tl, int tr, int v) {
		if(r < tl or tr < l)return {1e9, 1e9};
		if(l <= tl and tr<=r)return T[v];
		push(v);
		int tm=(tl+tr)/2;
		return min(query(l, r, tl, tm, 2*v), query(l, r, tm+1, tr, 2*v+1));
	}
	void update(int l, int r, int add) {
		update(l, r, add, 0, n-1, 1);
	}
	pair<int,int> query(int l, int r) {
		return query(l, r, 0, n-1, 1);
	}
};
const int N = 2e5+10;
vector<int> H;
vector<int> g[N];
int sml[N], grt[N];
int k;
int n;
void init(int K, std::vector<int> r) {
	k=K;
	n = r.size();
	lazy_segtree ls(r);
	int cnt = n;
	H.resize(n, -1);
	auto dfs = [&](int at, auto &&dfs) -> void {
		if(at >= k-1) {
			pair<int,int> val = ls.query(at-k+1, at-1);
			while(val.first == 0) {
				dfs(val.second, dfs);
				val = ls.query(at-k+1, at-1);
			}
			H[at] = cnt--;
			ls.update(at-k+1, at-1, -1);
			ls.update(at, at, 1e9);
		}
		else {
			pair<int,int> val = min(ls.query(0, at-1), ls.query(n-k+at+1, n-1));
			while(val.first == 0) {
				dfs(val.second, dfs);
				val = min(ls.query(0, at-1), ls.query(n-k+at+1, n-1));
			}
			H[at] = cnt--;
			ls.update(0, at-1, -1), ls.update(n-k+at+1, n-1, -1);
			ls.update(at, at, 1e9);
		}
	};
	while(ls.query(0, n-1).first == 0) {
		dfs(ls.query(0, n-1).second, dfs);
	}
	for(int i = 0;i<n;i++) {
		H.push_back(H[i]);
	}
	for(int i =0 ;i<2*n;i++) {
		int nxtmn = -1;
		for(int j = i+1;j<min(2*n, i+k);j++) {
			if(H[j] < H[i] and (nxtmn == -1 or H[nxtmn] < H[j])) {
				nxtmn = j;
			}
		}
		sml[i] = nxtmn;
		nxtmn = -1;
		for(int j = i+1;j<min(2*n, i+k);j++) {
			if(H[j] > H[i] and (nxtmn == -1 or H[nxtmn] > H[j])) {
				nxtmn = j;
			}
		}
		grt[i] = nxtmn;
//		cout << i << " " <<  H[i] << " " << sml[i] << " " << grt[i] << endl;
	}
	return;
}
int dist(int a, int b) {
	return min({abs(a-b), abs(a+n-b), abs(b+n-a)});
}
int compare_plants(int x, int y) {
	{
		int a = x, b = y;
		if(b < a)b+=n;
		while(a!=-1 and a + k -1 < b) {
			a=grt[a];
		}
		if(a!=-1 and H[a]<H[b])return -1;
		a=x;
		while(a!=-1 and a + k -1 < b) {
			a=sml[a];
		}
		if(a!=-1 and H[a]>H[b])return 1;
	}
	{
		int a = y, b = x;
		if(b<a)b+=n;
		while(a!=-1 and a + k -1 < b) {
			a=grt[a];
		}
		if(a!=-1 and H[a]<H[b])return 1;
		a=y;
		while(a!=-1 and a + k -1 < b) {
			a=sml[a];
		}
		if(a!=-1 and H[a]>H[b])return -1;
	}
	return 0;
}

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