Submission #930951

#	Time	Username	Problem	Language	Result	Execution time	Memory
930951		horiseun	Two Antennas (JOI19_antennas)	C++17	100 / 100	919 ms	98152 KiB

antennas

#include <iostream>
#include <vector>
#include <tuple>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <array>
#include <random>
#include <climits>
#include <cassert>
#include <algorithm>
#include <functional>
using namespace std;

template<typename A, typename B> ostream& operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator << (ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) { os << sep << x, sep = ", "; } return os << '}'; }
void D_out() { cerr << endl; }
template<typename Head, typename... Tail> void D_out(Head H, Tail... T) { cerr << ' ' << H; D_out(T...); }

#ifdef DEBUG
	#define D(...) cerr << '(' << #__VA_ARGS__ << "):", D_out(__VA_ARGS__)
#else
	#define D(...)
#endif

#define int long long
#define ll long long
#define ld long double
#define f first
#define s second
#define sz(x) ((int) x.size())
#define all(x) (x).begin(), (x).end()

const ll MOD = 1e9 + 7;
const ll INF = 1e18;

struct Node {
	int l, r, c, d, lazy;
	Node *lft, *rht;
	Node (int tl, int tr): l(tl), r(tr), c(0), d(-1), lazy(1e18) {
		if (l + 1 != r) {
			lft = new Node(l, (l + r) / 2);
			rht = new Node((l + r) / 2, r);
		} else {
			lft = rht = NULL;
		}
	}
};

void propagate(Node *x) {
	if (x->lazy != 1e18) {
		x->d = max(x->d, x->c - x->lazy);
		if (x->lft) x->lft->lazy = min(x->lft->lazy, x->lazy);
		if (x->rht) x->rht->lazy = min(x->rht->lazy, x->lazy);
		x->lazy = 1e18;
	}	
}

void update1(Node *x, int pos, int v) {
	propagate(x);
	if (pos < x->l || x->r <= pos) {
		return;
	}
	if (x->l + 1 == x->r) {
		x->c = v;
		return;
	}
	update1(x->lft, pos, v);
	update1(x->rht, pos, v);
	x->c = max(x->lft->c, x->rht->c);
	x->d = max(x->lft->d, x->rht->d);
}

void update2(Node *x, int l, int r, int v) {
	propagate(x);
	if (r <= x->l || x->r <= l) {
		return;
	}
	if (l <= x->l && x->r <= r) {
		x->lazy = v;
		propagate(x);
		return;
	}
	update2(x->lft, l, r, v);
	update2(x->rht, l, r, v);
	x->c = max(x->lft->c, x->rht->c);
	x->d = max(x->lft->d, x->rht->d);
}

int query(Node *x, int l, int r) {
	propagate(x);
	if (r <= x->l || x->r <= l) {
		return -1e18;
	}
	if (l <= x->l && x->r <= r) {
		return x->d;
	}
	return max(query(x->lft, l, r), query(x->rht, l, r));
}

int n, q, ans[200005];
vector<array<int, 3>> v;
vector<pair<int, int>> queries, currq[200005];
vector<int> make[200005], kill[200005];
Node *root;

void solve() {
	cin >> n;
	v.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i][0] >> v[i][1] >> v[i][2];
	}
	cin >> q;
	for (int i = 0, l, r; i < q; i++) {
		cin >> l >> r;
		l--;
		r--;
		queries.push_back({l, r});
	}
	fill(ans, ans + 200005, -1);
	function<void()> sweep = [&] () {
		root = new Node(0, 200005);
		for (int i = 0; i < 200005; i++) {
			currq[i].clear();
			make[i].clear();
			kill[i].clear();
		}
		for (int i = 0; i < q; i++) {
			currq[queries[i].s].push_back({queries[i].f, i});
		}
		for (int i = 0; i < n; i++) {
			if (i + v[i][1] < n) {
				make[i + v[i][1]].push_back(i);	
			}
			if (i + v[i][2] < n) {
				kill[i + v[i][2]].push_back(i);
			}
			for (int j : make[i]) {
				update1(root, j, v[j][0]);
			}
			if (i - v[i][1] >= 0) {
				update2(root, max(i - v[i][2], 0ll), i - v[i][1] + 1, v[i][0]);
			}
			for (pair<int, int> j : currq[i]) {
				ans[j.s] = max(ans[j.s], query(root, j.f, i + 1));
			}
			for (int j : kill[i]) {
				update1(root, j, 0);
			}
		}
	};
	sweep();
	reverse(all(v));
	D(queries);
	for (pair<int, int> &q : queries) {
		int nqf = n - q.s - 1, nqs = n - q.f - 1;
		q = {nqf, nqs};
	}
	D(queries);
	sweep();
	for (int i = 0; i < q; i++) {
		cout << ans[i] << "\n";
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);	

	int t = 1; //cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		//cout << "Case #" << tc << ": ";
		solve();
	}
}

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