Submission #907371

#	Time	Username	Problem	Language	Result	Execution time	Memory
907371		mickey080929	Two Antennas (JOI19_antennas)	C++17	0 / 100	192 ms	36436 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

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

struct Tag{
	int mx, mn;
};

struct SegmentTree{
	vector<Node> tree;
	vector<Tag> lazy;
	void init(int n) {
		int 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(int node, int s, int 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].mx = -inf;
		lazy[node].mn = inf;
	}
	void update(int node, int s, int e, int l, int r, int 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;
		}
		int 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(int node, int s, int e, int tar, int val) {
		propagate(node, s, e);
		if (s > tar || tar > e) return;
		if (s == e) {
			if (val >= 0)
				tree[node] = {val, val, -1};
			else
				tree[node] = {-inf, inf, -1};
			return;
		}
		int 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]);
	}
	int query(int node, int s, int e, int l, int r) {
		propagate(node, s, e);
		if (l > e || s > r) return -1;
		if (l <= s && e <= r) return tree[node].ans;
		int mid = s + e >> 1;
		return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
	}
};

SegmentTree seg;

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

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL); 
	int n;
	cin >> n;
	for (int 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);
	}
	int q;
	cin >> q;
	for (int i=1; i<=q; i++) {
		cin >> l[i] >> r[i];
		qrs[r[i]].push_back(i);
	}
	seg.init(n);
	for (int 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 (int i=1; i<=q; i++) {
		cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

antennas.cpp: In member function 'void SegmentTree::init(int)':
antennas.cpp:19:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   19 |   int sz = 1 << __lg(n-1) + 2;
      |                 ~~~~~~~~~~^~~
antennas.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
antennas.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid = s + e >> 1;
      |             ~~^~~
antennas.cpp: In member function 'void SegmentTree::modify(int, int, int, int, int)':
antennas.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   int mid = s + e >> 1;
      |             ~~^~~
antennas.cpp: In member function 'int SegmentTree::query(int, int, int, int, int)':
antennas.cpp:69:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   int mid = s + e >> 1;
      |             ~~^~~

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