Submission #986033

#	Time	Username	Problem	Language	Result	Execution time	Memory
986033		OAleksa	Two Antennas (JOI19_antennas)	C++14	22 / 100	376 ms	63376 KiB

antennas

#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N = 2e5 + 69;
const int inf = 1e18;
int n, q, h[N], a[N], b[N], ans[N];
int mn[4 * N], mx[4 * N];
int lmn[4 * N], lmx[4 * N];
vector<pair<int, int>> st;
vector<pair<int, int>> rr[N], qs[N];
vector<pair<int, int>> ll[N], qss[N];
void push(int v) {
	if (lmx[v] != -inf) {
		mx[v * 2] = max(mx[v * 2], lmx[v]);
		mx[v * 2 + 1] = max(mx[v * 2 + 1], lmx[v]);
		lmx[v * 2] = max(lmx[v * 2], lmx[v]);
		lmx[v * 2 + 1] = max(lmx[v * 2 + 1], lmx[v]);
		lmx[v] = -inf;
	}
	if (lmn[v] != inf) {
		mn[v * 2] = min(mn[v * 2], mn[v]);
		mn[v * 2 + 1] = min(mn[v * 2 + 1], mn[v]);
		lmn[v * 2] = min(lmn[v * 2], lmn[v]);
		lmn[v * 2 + 1] = min(lmn[v * 2 + 1], lmn[v]);
		lmn[v] = inf;
	}
}
void modify(int v, int tl, int tr, int l, int r, int x) {
	if (tl > r || tr < l)
		return;
	else if (tl >= l && tr <= r) {
		lmn[v] = min(lmn[v], x);
		lmx[v] = max(lmx[v], x);
		mn[v] = min(mn[v], x);
		mx[v] = max(mx[v], x);
	}
	else {
		push(v);
		int mid = (tl + tr) / 2;
		modify(v * 2, tl, mid, l, r, x);
		modify(v * 2 + 1, mid + 1, tr, l, r, x);
		mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
		mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
	}
}

void reset(int v, int tl, int tr, int p) {
	if (tl == tr) {
		mx[v] = -inf;
		mn[v] = inf;
	}
	else {
		int mid = (tl + tr) / 2;
		push(v);
		if (p <= mid)
			reset(v * 2, tl, mid, p);
		else
			reset(v * 2 + 1, mid + 1, tr, p);
		mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
		mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	}
}
int getmin(int v, int tl, int tr, int p) {
	if (tl == tr)
		return mn[v];
	else {
		int mid = (tl + tr) / 2;
		push(v);
		if (p <= mid)
			return getmin(v * 2, tl, mid, p);
		else
			return getmin(v * 2 + 1, mid + 1, tr, p);
	}
}
int getmax(int v, int tl, int tr, int p) {
	if (tl == tr)
		return mx[v];
	else {
		int mid = (tl + tr) / 2;
		push(v);
		if (p <= mid)
			return getmax(v * 2, tl, mid, p);
		else
			return getmax(v * 2 + 1, mid + 1, tr, p);
	}
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n;
  	for (int i = 1;i <= n;i++) 
  		cin >> h[i] >> a[i] >> b[i];
		for (int i = 0;i < 4 * N;i++) {
			mn[i] = lmn[i] = inf;
			mx[i] = lmx[i] = -inf;
  	}
  	for (int i = 1;i <= n;i++) {
  		int l, r;
  		l = i + a[i];
  		r = i + b[i];
  		if (l <= n) {
  			r = min(r, n);
  			rr[l].push_back({i, -1});
  			rr[r].push_back({i, 1});
  		}
  		l = i - b[i];
  		r = i - a[i];
  		if (r >= 1) {
  			l = max(l, 1ll);
  			ll[r].push_back({i, -1});
  			ll[l].push_back({i, 1});
  		}
  	}
  	cin >> q;
  	for (int i = 1;i <= q;i++) {
  		int l, r;
  		cin >> l >> r;
  		ans[i] = -1;
  		qs[r].push_back({l, i});
  		qss[l].push_back({r, i});
  	}
  	for (int i = 1;i <= n;i++) {
  		for (auto j : rr[i]) {
  			int id = j.f, f = j.s;
  			if (f == -1)
  				reset(1, 1, n, id);
  		}
  		int l = i - b[i];
  		int r = i - a[i];
  		if (r >= 1) {
  			l = max(l, 1ll);
  			modify(1, 1, n, l, r, h[i]);
  		}
  		for (auto j : rr[i]) {
  			int id = j.f, f = j.s;
  			if (f == 1) {
  				int x = getmin(1, 1, n, id);
  				int y = getmax(1, 1, n, id);
  				int b = -1;
  				if (x != inf)
  					b = abs(h[id] - x);
  				if (y != -inf)
  					b = abs(h[id] - y);
  				if (b != -1) {
  					while (!st.empty() && st.back().f <= b)
  						st.pop_back();
  					st.push_back({b, id});
  				}
  			}
  		}  		
  		for (auto j : qs[i]) {
  			int l = j.f, dd = j.s;
  			int x = 0, y = st.size() - 1, id = -1;
  			while (x <= y) {
  				int mid = (x + y) / 2;
  				if (st[mid].s >= l) {
  					id = mid;
  					y = mid - 1;
  				}
  				else
  					x = mid + 1;
  			}
  			if (id != -1)
  				ans[dd] = st[id].f;
  		}
  	}
  	for (int i = 0;i < 4 * N;i++) {
  		mn[i] = lmn[i] = inf;
  		mx[i] = lmx[i] = -inf;
  	}
  	deque<pair<int, int>> dq;
  	for (int i = n;i >= 1;i--) {
  		for (auto j : ll[i]) {
  			int id = j.f, f = j.s;
  			if (f == -1)
  				reset(1, 1, n, id);
  		}
  		int l = i + a[i];
  		int r = i + b[i];
  		if (l <= n) {
  			r = min(r, n);
  			modify(1, 1, n, l, r, h[i]);
  		}
  		for (auto j : ll[i]) {
  			int id = j.f, f = j.s;
  			if (f == 1) {
  				int x = getmin(1, 1, n, id);
  				int y = getmax(1, 1, n, id);
  				int b = -1;
  				if (x != inf)
  					b = abs(h[id] - x);
  				if (y != -inf)
  					b = abs(h[id] - y);
  				if (b != -1) {
  					while (!dq.empty() && dq.front().f <= b)
  						dq.pop_front();
  					dq.push_front({b, id});
  				}
  			}
  		} 
  		for (auto j : qss[i]) {
  			int r = j.f, dd = j.s;
  			int x = 0, y = dq.size() - 1, id = -1;
  			while (x <= y) {
  				int mid = (x + y) / 2;
  				if (dq[mid].s <= r) {
  					id = mid;
  					x = mid + 1;
  				}
  				else
  					y = mid - 1;
  			}
  			if (id != -1)
  				ans[dd] = max(ans[dd], dq[id].f);
  		}
  	}
  	for (int i = 1;i <= q;i++) {
  		cout << ans[i] << '\n';
  	}
  }
  return 0; 
}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:97:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   97 |    for (int i = 1;i <= n;i++)
      |    ^~~
antennas.cpp:99:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   99 |   for (int i = 0;i < 4 * N;i++) {
      |   ^~~

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