Submission #1217048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217048		siewjh	Bodyguard (JOI21_bodyguard)	C++20	100 / 100	3445 ms	1595228 KiB

bodyguard

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXQ = 3000005;
const ll inf = 1e18;
ll ans[MAXQ];
vector<ll> xdisc, ydisc;
struct line{
	ll m, c;
	ll eval(ll x){
		return m * x + c;
	}
};
struct node{
	ll s, e, m; line ln;
	node *l = nullptr, *r = nullptr;
	node(ll _s, ll _e) {
		s = _s, e = _e, m = (s + e) >> 1, ln = { 0, -inf };
	}
	void makechild() {
		if (l == nullptr) {
			l = new node(s, m); r = new node(m, e);
		}
	}
	void update(line x) {
		if (x.eval(m) > ln.eval(m)) swap(ln, x);
		if (s + 1 == e || x.c == -inf) return;
		if (x.eval(s) > ln.eval(s)) {
			makechild(); l->update(x);
		}
		else if (x.eval(e) > ln.eval(e)) {
			makechild(); r->update(x);
		}
	}
	ll query(ll x) {
		if (l == nullptr || s + 1 == e) return ln.eval(x);
		if (x < m) return max(ln.eval(x), l->query(x));
		else return max(ln.eval(x), r->query(x));
	}
};
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int nums, queries; cin >> nums >> queries;
	vector<tuple<ll, ll, ll, ll>> pv[2];
	for (int i = 0; i < nums; i++){
		ll t, a, b, c, s, e, o; cin >> t >> a >> b >> c;
		c >>= 1;
		if (a < b){
			s = t + a, e = s + 2 * (b - a), o = t - a;
			xdisc.push_back(s); xdisc.push_back(e); ydisc.push_back(o);
			pv[0].push_back({s, e, o, c});
		}
		else{
			s = t - a, e = s + 2 * (a - b), o = t + a;
			ydisc.push_back(s); ydisc.push_back(e); xdisc.push_back(o);
			pv[1].push_back({s, e, o, c});
		}
	}
	sort(xdisc.begin(), xdisc.end());
	xdisc.resize(distance(xdisc.begin(), unique(xdisc.begin(), xdisc.end())));
	sort(ydisc.begin(), ydisc.end());
	ydisc.resize(distance(ydisc.begin(), unique(ydisc.begin(), ydisc.end())));
	int xsz = xdisc.size(), ysz = ydisc.size();
	vector<vector<ll>> hpay(ysz, vector<ll>(xsz));
	vector<vector<vector<pair<bool, ll>>>> hpv(ysz, vector<vector<pair<bool, ll>>>(xsz + 1));
	for (auto [s, e, o, c] : pv[0]){
		s = lower_bound(xdisc.begin(), xdisc.end(), s) - xdisc.begin();
		e = lower_bound(xdisc.begin(), xdisc.end(), e) - xdisc.begin();
		o = lower_bound(ydisc.begin(), ydisc.end(), o) - ydisc.begin();
		hpv[o][s + 1].push_back({0, c}); hpv[o][e + 1].push_back({1, c});
	}
	for (int o = 0; o < ysz; o++){
		multiset<ll> s; s.insert(0);
		for (int i = 0; i < xsz; i++){
			for (auto [typ, c] : hpv[o][i]){
				if (typ) s.erase(s.find(c));
				else s.insert(c);
			}
			hpay[o][i] = *s.rbegin();
		}
	}
	vector<vector<ll>> vpay(xsz, vector<ll>(ysz));
	vector<vector<vector<pair<bool, ll>>>> vpv(xsz, vector<vector<pair<bool, ll>>>(ysz + 1));
	for (auto [s, e, o, c] : pv[1]){
		s = lower_bound(ydisc.begin(), ydisc.end(), s) - ydisc.begin();
		e = lower_bound(ydisc.begin(), ydisc.end(), e) - ydisc.begin();
		o = lower_bound(xdisc.begin(), xdisc.end(), o) - xdisc.begin();
		vpv[o][s + 1].push_back({0, c}); vpv[o][e + 1].push_back({1, c});
	}
	for (int o = 0; o < xsz; o++){
		multiset<ll> s; s.insert(0);
		for (int i = 0; i < ysz; i++){
			for (auto [typ, c] : vpv[o][i]){
				if (typ) s.erase(s.find(c));
				else s.insert(c);
			}
			vpay[o][i] = *s.rbegin();
		}
	}
	vector<vector<ll>> dp(xsz, vector<ll>(ysz));
	for (int x = xsz - 1; x >= 0; x--)
		for (int y = ysz - 1; y >= 0; y--){
			dp[x][y] = 0;
			if (x != xsz - 1) dp[x][y] = max(dp[x][y], dp[x + 1][y] + hpay[y][x + 1] * (xdisc[x + 1] - xdisc[x]));
			if (y != ysz - 1) dp[x][y] = max(dp[x][y], dp[x][y + 1] + vpay[x][y + 1] * (ydisc[y + 1] - ydisc[y]));
		}
	vector<vector<tuple<int, ll, int>>> hqv(ysz), vqv(xsz);
	for (int q = 0; q < queries; q++){
		ll t, p; cin >> t >> p;
		ll x = t + p, y = t - p;
		int xid = lower_bound(xdisc.begin(), xdisc.end(), x) - xdisc.begin();
		int yid = lower_bound(ydisc.begin(), ydisc.end(), y) - ydisc.begin();
		if (xid != xsz && yid != ysz){
			hqv[yid].push_back({xid, y, q}); vqv[xid].push_back({yid, x, q}); 
		}
	}
	for (int i = 0; i < ysz; i++){
		sort(hqv[i].begin(), hqv[i].end(), greater<tuple<int, ll, int>>());
		int curr = xsz;
		if (i != 0){
			node *root = new node(0, ydisc[i] - ydisc[i - 1]);
			for (auto [id, y, q] : hqv[i]){
				while (curr > id){
					curr--; root->update({vpay[curr][i], dp[curr][i]});
				}
				ans[q] = max(ans[q], root->query(ydisc[i] - y));
			}	
		}
		else{
			ll maxv = 0;
			for (auto [id, y, q] : hqv[i]){
				while (curr > id){
					curr--; maxv = max(maxv, dp[curr][i]);
				}
				ans[q] = max(ans[q], maxv);
			}	
		}
	}
	for (int i = 0; i < xsz; i++){
		sort(vqv[i].begin(), vqv[i].end(), greater<tuple<int, ll, int>>());
		int curr = ysz;
		if (i != 0){
			node *root = new node(0, xdisc[i] - xdisc[i - 1]);
			for (auto [id, x, q] : vqv[i]){
				while (curr > id){
					curr--; root->update({hpay[curr][i], dp[i][curr]});
				}
				ans[q] = max(ans[q], root->query(xdisc[i] - x));
			}
		}
		else{
			ll maxv = 0;
			for (auto [id, x, q] : vqv[i]){
				while (curr > id){
					curr--; maxv = max(maxv, dp[i][curr]);
				}
				ans[q] = max(ans[q], maxv);
			}
		}
	}
	for (int q = 0; q < queries; q++) cout << ans[q] << '\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 52 / 52