Submission #1219020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219020		bangan	송신탑 (IOI22_towers)	C++20	56 / 100	642 ms	11532 KiB

towers

// Fuck It We BALL

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

#define chmax(a, b) a = max(a, b)

#define pb push_back
#define ALL(a) a.begin(), a.end()

#define LC (v<<1)
#define RC (LC|1)
#define mid ((l+r) / 2)

const int mxn = 1e5 + 4;

int n;
int h[mxn];

struct MinRangeSeg {
	struct Node {
		int idx, val;
		Node() {}
		Node(int idx_, int val_): idx(idx_), val(val_) {}
	};
	int n;
	vector<Node> t; 
	MinRangeSeg(int n_): n(n_), t(4*n_ + 16) {}
	void pull(int v) {
		t[v] = t[LC];
		if (t[v].val > t[RC].val) t[v] = t[RC];
	}
	void set_val(int i, int x, int v, int l, int r) {
		if (r-l == 1) {
			t[v] = Node(i, x);
			return;
		}
		i<mid ? set_val(i,x, LC, l, mid) : set_val(i,x, RC, mid, r);
		pull(v);
	}
	void set_val(int i, int x) {
		set_val(i,x, 1, 0, n);
	}
	Node get_min(int s, int e, int v, int l, int r) {
		if (s<=l && r<=e) return t[v];
		if (e <= mid) return get_min(s,e, LC, l, mid);
		if (s >= mid) return get_min(s,e, RC, mid, r);
		Node L = get_min(s,e, LC, l, mid);
		Node R = get_min(s,e, RC, mid, r);
		return L.val < R.val ? L : R;
	}
	Node get_min(int s, int e) {
		return get_min(s, e, 1, 0, n);
	}
} seg_min_h(mxn), seg_min_nxt(mxn);

struct MaxRangeSeg {
	struct Node {
		int idx, val;
		Node() {}
		Node(int idx_, int val_): idx(idx_), val(val_) {}
	};
	int n;
	vector<Node> t; 
	MaxRangeSeg(int n_): n(n_), t(4*n_ + 16) {}
	void pull(int v) {
		t[v] = t[LC];
		if (t[v].val < t[RC].val) t[v] = t[RC];
	}
	void set_val(int i, int x, int v, int l, int r) {
		if (r-l == 1) {
			t[v] = Node(i, x);
			return;
		}
		i<mid ? set_val(i,x, LC, l, mid) : set_val(i,x, RC, mid, r);
		pull(v);
	}
	void set_val(int i, int x) {
		set_val(i,x, 1, 0, n);
	}
	Node get_max(int s, int e, int v, int l, int r) {
		if (s<=l && r<=e) return t[v];
		if (e <= mid) return get_max(s,e, LC, l, mid);
		if (s >= mid) return get_max(s,e, RC, mid, r);
		Node L = get_max(s,e, LC, l, mid);
		Node R = get_max(s,e, RC, mid, r);
		return L.val > R.val ? L : R;
	}
	Node get_max(int s, int e) {
		return get_max(s, e, 1, 0, n);
	}
} seg_max_h(mxn), seg_max_prv(mxn);

void init(int N, std::vector<int> H) {
	n = N;
	for (int i=0; i<n; i++) h[i+1] = H[i]; 
	for (int i=1; i<=n; i++) seg_min_h.set_val(i, h[i]);
	for (int i=1; i<=n; i++) seg_max_h.set_val(i, h[i]);
}

int prv[mxn], nxt[mxn];
vector<int> stk;
bool is[mxn];
int can_prv[mxn], can_nxt[mxn];

void prep(int d) {
	for (int i=1; i<=n; i++) {
		int l = 0, r = i;
		while (r-l > 1) {
			h[i] <= seg_max_h.get_max(mid, i).val - d ? l = mid : r = mid;
		}
		prv[i] = l;
		seg_max_prv.set_val(i, prv[i]);
		// if (1 <= l) assert(h[i] <= h[l]-d);
	}
	for (int i=1; i<=n; i++) {
		int l = i, r = n+1;
		while (r-l > 1) {
			h[i] <= seg_max_h.get_max(i+1, mid+1).val - d ? r = mid : l = mid;
		}
		nxt[i] = r;
		seg_min_nxt.set_val(i, nxt[i]);
		// if (r <= n) assert(h[i] <= h[r]-d);
	}
	// for (int i=1; i<=n; i++) {
	// 	for (int j = i-1; j>=1; j--) if (h[i] <= h[j]-d) {
	// 		// cout << prv[i] << " correct = " << j << endl;
	// 		assert(prv[i]==j);
	// 		break;
	// 	}
	// }
	// for (int i=1; i<=n; i++) {
	// 	for (int j = i+1; j<=n; j++) if (h[i] <= h[j]-d) {
	// 		// cout << nxt[i] << " correct = " << j << endl;
	// 		assert(nxt[i]==j);
	// 		break;
	// 	}
	// }

	stk = {1};
	{
		int mx = 0;
		for (int i = 2; i <= n; i++) {
			if (h[i] <= mx-d && h[stk.back()] <= mx-d) stk.pb(i), mx=0;
			else if (h[i] < h[stk.back()]) {
				stk.pop_back();
				stk.pb(i);
				mx=0;
			}
			else chmax(mx, h[i]);
		}
	}

	for (int i : stk) is[i] = 1;
	for (int i = stk[0]+1, mx=0, lst=stk[0]; i<=n; i++) {
		if (is[i]) {
			mx=0;
			lst=i;
			continue;
		}
		if (h[i] <= mx-d && h[lst] <= mx-d) can_prv[i] = 1;
		chmax(mx, h[i]);
	}
	for (int i = stk.back()-1, mx=0, lst=stk.back(); i>=1; i--) {
		if (is[i]) {
			mx=0;
			lst=i;
			continue;
		}
		if (h[i] <= mx-d && h[lst] <= mx-d) can_nxt[i] = 1;
		chmax(mx, h[i]);
	}
	for (int i=1; i <= n+1; i++) {
		can_prv[i] += can_prv[i-1];
		can_nxt[i] += can_nxt[i-1];
	}
}

bool DONE = false;
int max_towers(int L, int R, int D) {
	L++; R++;
	if (!DONE) {
		prep(D);
		DONE = true;
	}
	int l = lower_bound(ALL(stk), L) - stk.begin();
	int r = upper_bound(ALL(stk), R) - stk.begin();
	if (l==r) {
		int i = seg_min_h.get_min(L, R+1).idx;
		int ans = 1;
		if (i != L && seg_min_nxt.get_min(L, i).val < i) ans = 2;
		if (i != R && seg_max_prv.get_max(i+1, R+1).val > i) ans = 2;
		return ans;
	}
	else {
		int ans = r-l;
		r--;
		l = stk[l];
		r = stk[r];
		if (can_nxt[l-1] - can_nxt[L-1] != 0) ans++;
		if (can_prv[R]   - can_prv[r]   != 0) ans++;
		return ans;
	}
	return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 0 / 17
• Subtask 6: 19 / 19
• Subtask 7: 0 / 23