Submission #986161

#	Time	Username	Problem	Language	Result	Execution time	Memory
986161		OAleksa	Two Antennas (JOI19_antennas)	C++14	100 / 100	655 ms	73664 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 mx[4 * N], lmx[4 * N], st[4 * N];
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]);
		st[v * 2] = max(st[v * 2], mx[v * 2] + lmx[v]);
		st[v * 2 + 1] = max(st[v * 2 + 1], 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;
	}
}
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) {
		lmx[v] = max(lmx[v], x);
		st[v] = max(st[v], x + mx[v]);
	}
	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]);
		st[v] = max(st[v * 2], st[v * 2 + 1]);
	}
}

void upd(int v, int tl, int tr, int p, int x) {
	if (tl == tr) 
		mx[v] = x;
	else {
		int mid = (tl + tr) / 2;
		push(v);
		if (p <= mid)
			upd(v * 2, tl, mid, p, x);
		else
			upd(v * 2 + 1, mid + 1, tr, p, x);
		mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	}
}
int get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return -inf;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		push(v);
		return max(get(v * 2, tl, mid, l, r), get(v * 2 + 1, mid + 1, tr, l, r));    
	}
}
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++) 
			mx[i] = lmx[i] = st[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) {
  				upd(1, 1, n, id, h[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 : qs[i]) {
  			int l = j.f, dd = j.s;
  			int x = get(1, 1, n, l, i);
  			ans[dd] = max(ans[dd], x);
  		}
  		for (auto j : rr[i]) {
  			int id = j.f, f = j.s;
  			if (f == 1) 
  				upd(1, 1, n, id, -inf);
  		}  		
  	}
  	for (int i = 0;i < 4 * N;i++)
  		mx[i] = lmx[i] = st[i] = -inf;
  	for (int i = n;i >= 1;i--) {
  		for (auto j : ll[i]) {
  			int id = j.f, f = j.s;
  			if (f == -1)
  				upd(1, 1, n, id, h[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 : qss[i]) {
  			int r = j.f, dd = j.s;
  			int x = get(1, 1, n, i, r);
  			if (x >= inf)
  				continue;
  			ans[dd] = max(ans[dd], get(1, 1, n, i, r));
  		}
  		for (auto j : ll[i]) {
  			int id = j.f, f = j.s;
  			if (f == 1) {
  				upd(1, 1, n, id, -inf);
  			}
  		} 
  	}
  	for (int i = 1;i <= q;i++) {
  		cout << ans[i] << '\n';
  	}
  }
  return 0; 
}

Compilation message (stderr)

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

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