Submission #626019

#	Time	Username	Problem	Language	Result	Execution time	Memory
626019		happypotato	Radio Towers (IOI22_towers)	C++17	41 / 100	4042 ms	8640 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll int, ll int>
#define ff first
#define ss second
#define pb push_back
// globals
const int mxN = 1e5 + 1;
const int MIN = -1e9, MAX = 1e9;
bool isst1 = true;
int st1point;
int n;
vector<int> h;
int peaks[mxN];
void init(int N, vector<int> H) {
	n = N; h = H;
	if (true) {
		bool isasc = true;
		for (int i = 1; i < n; i++) {
			if (h[i - 1] < h[i]) {
				if (!isasc) {
					isst1 = false;
					break;
				}
			} else {
				if (isasc) {
					isasc = false;
					st1point = i - 1;
				}
			}
		}
		if (isasc) st1point = n - 1;
	}
	if (isst1) return;
	peaks[0] = peaks[1] = 0;
	for (int i = 1; i < n; i++) {
		peaks[i + 1] = peaks[i] + (h[i - 1] < h[i] && h[i] > h[i + 1]);
	}
	peaks[n] = peaks[n - 1];
}
// Q = 1
int take[mxN], tower[mxN];
pii seg[4 * mxN];
pii lazy[4 * mxN];
bool marked[4 * mxN];
void pushup(int idx) {
	seg[idx].ff = max(seg[(idx << 1)].ff, seg[(idx << 1) | 1].ff);
	seg[idx].ss = min(seg[(idx << 1)].ss, seg[(idx << 1) | 1].ss);
}
void pushdown(int idx) {
	if (marked[idx]) {
		if (lazy[idx].ff != MAX) {
			seg[(idx << 1)].ff = min(seg[(idx << 1)].ff, lazy[idx].ff);
			seg[(idx << 1) | 1].ff = min(seg[(idx << 1) | 1].ff, lazy[idx].ff);
			lazy[(idx << 1)].ff = min(lazy[(idx << 1)].ff, lazy[idx].ff);
			lazy[(idx << 1) | 1].ff = min(lazy[(idx << 1) | 1].ff, lazy[idx].ff);
			lazy[idx].ff = MAX;
		}
		if (lazy[idx].ss != MIN) {
			seg[(idx << 1)].ss = max(seg[(idx << 1)].ss, lazy[idx].ss);
			seg[(idx << 1) | 1].ss = max(seg[(idx << 1) | 1].ss, lazy[idx].ss);
			lazy[(idx << 1)].ss = max(lazy[(idx << 1)].ss, lazy[idx].ss);
			lazy[(idx << 1) | 1].ss = max(lazy[(idx << 1) | 1].ss, lazy[idx].ss);
			lazy[idx].ss = MIN;
		}
		marked[(idx << 1)] = true;
		marked[(idx << 1) | 1] = true;
		marked[idx] = false;
	}
}
void build() {
	for (int i = 0; i < 4 * mxN; i++) {
		seg[i] = {MAX, MIN};
		lazy[i] = {MAX, MIN};
	}
}
void update(int tl, int tr, bool istower, int val, int l = 1, int r = n, int idx = 1) {
	if (tl > tr) return;
	if (tl <= l && r <= tr) {
		if (!istower) {
			seg[idx].ff = min(seg[idx].ff, val);
			lazy[idx].ff = min(lazy[idx].ff, val);
		} else {
			seg[idx].ss = max(seg[idx].ss, val);
			lazy[idx].ss = max(lazy[idx].ss, val);
		}
		marked[idx] = true;
		return;
	}
	pushdown(idx);
	int mid = (l + r) >> 1;
	if (tl <= mid) update(tl, min(tr, mid), istower, val, l, mid, (idx << 1));
	if (tr > mid) update(max(tl, mid + 1), tr, istower, val, mid + 1, r, (idx << 1) | 1);
	pushup(idx);
}
// query1 for finding takes: min s.t. < curval (-1 by hand)
int query1(int val, int l = 1, int r = n, int idx = 1) {
	// cerr << val << ' ' << l << ' ' << r << ' ' << seg[idx].ss << endl;
	if (seg[idx].ss >= val) return -1;
	if (l == r) return l;
	pushdown(idx);
	int mid = (l + r) >> 1;
	int ret = 0;
	ret = query1(val, l, mid, (idx << 1));
	if (ret != -1) return ret;
	ret = query1(val, mid + 1, r, (idx << 1) + 1);
	if (ret != -1) return ret;
	throw runtime_error("segtree died 1");
}
// query2 for finding towers: min s.t. > curval (-1 by hand)
int query2(int val, int l = 1, int r = n, int idx = 1) {
	// cerr << val << ' ' << l << ' ' << r << ' ' << seg[idx].ff << endl;
	if (seg[idx].ff <= val) return -1;
	if (l == r) return l;
	pushdown(idx);
	int mid = (l + r) >> 1;
	int ret = 0;
	ret = query2(val, l, mid, (idx << 1));
	if (ret != -1) return ret;
	ret = query2(val, mid + 1, r, (idx << 1) | 1);
	if (ret != -1) return ret;
	throw runtime_error("segtree died 2");
}
int max_towers(int L, int R, int D) {
	if (isst1) {
		if (L < st1point && st1point < R && h[st1point] - max(h[L], h[R]) >= D) return 2;
		else return 1;
	} else if (D == 1) {
		L++; R++;
		return 1 + max(0, peaks[R - 1] - peaks[L]);
	}
	build();
	// cerr << "CUR " << L << endl;
	take[L] = 1;
	tower[L] = 0;
	update(1, 1, false, h[L]);
	int ans = 1;
	int cnt = 1;
	for (int i = L + 1; i <= R; i++) {
		// cerr << "CUR " << i << endl;
		// tower
		tower[i] = query2(h[i] - D);
		if (tower[i] == -1) tower[i] = cnt;
		else tower[i]--;
		// cerr << "TOWER: " << tower[i] << endl;
		update(1, tower[i], true, h[i]);
		// take
		take[i] = query1(h[i] + D);
		if (take[i] == -1) take[i] = ++cnt;
		// cerr << "TAKE: " << take[i] << endl;
		update(1, take[i], false, h[i]);
		ans = max(ans, take[i]);
	}
	return ans;
}

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