Submission #907382

#	Time	Username	Problem	Language	Result	Execution time	Memory
907382		mickey080929	Two Antennas (JOI19_antennas)	C++17	100 / 100	563 ms	61008 KiB

antennas

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll inf = 1e18;

struct Node{
	ll mx, mn, ans;
};

struct Tag{
	ll mx, mn;
};

struct SegmentTree{
	vector<Node> tree;
	vector<Tag> lazy;
	void init(ll n) {
		ll sz = 1 << __lg(n-1) + 2;
		tree.assign(sz, {-inf, inf, -1});
		lazy.assign(sz, {-inf, inf});
	}
	Node Merge(Node u, Node v) {
		return {max(u.mx, v.mx), min(u.mn, v.mn), max(u.ans, v.ans)};
	}
	void propagate(ll node, ll s, ll e) {
		tree[node].ans = max({tree[node].ans, lazy[node].mx - tree[node].mn, tree[node].mx - lazy[node].mn});
		if (s != e) {
			for (auto &i : {node*2, node*2+1}) {
				lazy[i].mx = max(lazy[i].mx, lazy[node].mx);
				lazy[i].mn = min(lazy[i].mn, lazy[node].mn);
			}
		}
		lazy[node] = {-inf, inf};
	}
	void update(ll node, ll s, ll e, ll l, ll r, ll val) {
		propagate(node, s, e);
		if (l > e || s > r) return;
		if (l <= s && e <= r) {
			lazy[node] = {val, val};
			propagate(node, s, e);
			return;
		}
		ll mid = s + e >> 1;
		update(node*2, s, mid, l, r, val);
		update(node*2+1, mid+1, e, l, r, val);
		tree[node] = Merge(tree[node*2], tree[node*2+1]);
	}
	void modify(ll node, ll s, ll e, ll tar, ll val) {
		propagate(node, s, e);
		if (s > tar || tar > e) return;
		if (s == e) {
			if (val >= 0) {
				tree[node].mx = val;
				tree[node].mn = val;
			}
			else {
				tree[node].mx = -inf;
				tree[node].mn = inf;
			}
			return;
		}
		ll mid = s + e >> 1;
		modify(node*2, s, mid, tar, val);
		modify(node*2+1, mid+1, e, tar, val);
		tree[node] = Merge(tree[node*2], tree[node*2+1]);
	}
	ll query(ll node, ll s, ll e, ll l, ll r) {
		propagate(node, s, e);
		if (l > e || s > r) return -1;
		if (l <= s && e <= r) return tree[node].ans;
		ll mid = s + e >> 1;
		return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
	}
};

SegmentTree seg;

ll h[200010], a[200010], b[200010];
ll l[200010], r[200010], ans[200010];
vector<ll> qrs[200010], add[200010], del[200010];

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL); 
	ll n;
	cin >> n;
	for (ll i=1; i<=n; i++) {
		cin >> h[i] >> a[i] >> b[i];
		if (i + a[i] <= n) add[i + a[i]].push_back(i);
		if (i + b[i] <= n) del[i + b[i]].push_back(i);
	}
	ll q;
	cin >> q;
	for (ll i=1; i<=q; i++) {
		cin >> l[i] >> r[i];
		qrs[r[i]].push_back(i);
	}
	seg.init(n);
	for (ll i=1; i<=n; i++) {
		for (auto &j : add[i]) seg.modify(1, 1, n, j, h[j]);
		seg.update(1, 1, n, i-b[i], i-a[i], h[i]);
		for (auto &j : qrs[i]) ans[j] = seg.query(1, 1, n, l[j], r[j]);
		for (auto &j : del[i]) seg.modify(1, 1, n, j, -1);
	}
	for (ll i=1; i<=q; i++) {
		cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

antennas.cpp: In member function 'void SegmentTree::init(ll)':
antennas.cpp:20:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   20 |   ll sz = 1 << __lg(n-1) + 2;
      |                ~~~~~~~~~~^~~
antennas.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll, ll)':
antennas.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   ll mid = s + e >> 1;
      |            ~~^~~
antennas.cpp: In member function 'void SegmentTree::modify(ll, ll, ll, ll, ll)':
antennas.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   ll mid = s + e >> 1;
      |            ~~^~~
antennas.cpp: In member function 'll SegmentTree::query(ll, ll, ll, ll, ll)':
antennas.cpp:73:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   ll mid = s + e >> 1;
      |            ~~^~~

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