Submission #670522

#	Time	Username	Problem	Language	Result	Execution time	Memory
670522		ymm	Two Antennas (JOI19_antennas)	C++17	100 / 100	455 ms	45232 KiB

antennas

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
const int inf = 1e9 + 10;

struct {
	int mnr, mxr;
	int mni, mxi;
	int mxv;
} seg[N*4];

void init(int i, int b, int e)
{
	seg[i] = {inf, -inf, inf, -inf, -inf};
	if (e-b == 1)
		return;
	init(2*i+1, b, (b+e)/2);
	init(2*i+2, (b+e)/2, e);
}

void insertr_node(int mn, int mx, int i)
{
	seg[i].mnr = min(seg[i].mnr, mn);
	seg[i].mxr = max(seg[i].mxr, mx);
	seg[i].mxv = max({seg[i].mxv, mx - seg[i].mni, seg[i].mxi - mn});
}

void ppg(int i)
{
	insertr_node(seg[i].mnr, seg[i].mxr, 2*i+1);
	insertr_node(seg[i].mnr, seg[i].mxr, 2*i+2);
	seg[i].mnr = inf;
	seg[i].mxr = -inf;
}

void up(int i)
{
	seg[i].mni = min(seg[2*i+1].mni, seg[2*i+2].mni);
	seg[i].mxi = max(seg[2*i+1].mxi, seg[2*i+2].mxi);
	seg[i].mxv = max(seg[2*i+1].mxv, seg[2*i+2].mxv);
}

void insertr(int l, int r, int x, int i, int b, int e)
{
	if (l <= b && e <= r) {
		insertr_node(x, x, i);
		return;
	}
	if (r <= b || e <= l)
		return;
	ppg(i);
	insertr(l, r, x, 2*i+1, b, (b+e)/2);
	insertr(l, r, x, 2*i+2, (b+e)/2, e);
	up(i);
}

void changei(int p, int x, int i, int b, int e)
{
	if (e-b == 1) {
		seg[i].mni = x == -1? inf: x;
		seg[i].mxi = x == -1? -inf: x;
		return;
	}
	ppg(i);
	if (p < (b+e)/2)
		changei(p, x, 2*i+1, b, (b+e)/2);
	else
		changei(p, x, 2*i+2, (b+e)/2, e);
	up(i);
}

int get(int l, int r, int i, int b, int e)
{
	if (l <= b && e <= r)
		return seg[i].mxv;
	if (r <= b || e <= l)
		return -inf;
	ppg(i);
	return max(get(l, r, 2*i+1, b, (b+e)/2),
	           get(l, r, 2*i+2, (b+e)/2, e));
}

int h[N], a[N], b[N];
vector<int> add[N];
vector<int> rem[N];
int ql[N], qr[N];
int qans[N];
vector<int> qvec[N];
int n, q;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n) {
		cin >> h[i] >> a[i] >> b[i];
		if (a[i] > b[i])
			swap(a[i], b[i]);
		if (i + a[i] < n)
			add[i + a[i]].push_back(i);
		if (i + b[i] + 1 < n)
			rem[i + b[i] + 1].push_back(i);
	}
	cin >> q;
	Loop (i,0,q) {
		cin >> ql[i] >> qr[i];
		--ql[i];
		qvec[qr[i]-1].push_back(i);
	}
	init(0, 0, n);
	Loop (i,0,n) {
		for (int j : add[i])
			changei(j, h[j], 0, 0, n);
		for (int j : rem[i])
			changei(j, -1, 0, 0, n);
		int l = max(0ll, i - b[i]);
		int r = min(i, i - a[i] + 1);
		if (l < r)
			insertr(l, r, h[i], 0, 0, n);
		for (int j : qvec[i])
			qans[j] = get(ql[j], qr[j], 0, 0, n);
	}
	Loop (i,0,q)
		cout << (qans[i] < 0? -1: qans[i]) << '\n';
}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65