Submission #457631

#	Time	Username	Problem	Language	Result	Execution time	Memory
457631		8e7	Bodyguard (JOI21_bodyguard)	C++17	42 / 100	25023 ms	417268 KiB

bodyguard

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 3005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct seg{
	pii st, ed;
	ll cost;
	seg(){st = {0, 0}, ed = {0, 0}, cost = 0;}
	seg(pii x, pii y, ll c){st = x, ed = y, cost = c;};
} arr[maxn];
vector<ll> xv, yv;
vector<vector<pii> > cost;
vector<vector<ll> > dp;
int main() {
	io
	int n, q;
	cin >> n >> q;
	auto turn = [&](pii p) {return make_pair((p.ff - p.ss), (p.ff + p.ss));};
	for (int i = 0;i < n;i++) {
		ll t, a, b, c;
		cin >> t >> a >> b >> c;
		pii p1 = {t, a}, p2 = {t + abs(b - a), b};
		p1 = turn(p1), p2 = turn(p2);
		arr[i] = seg(p1, p2, c / 2);
		xv.push_back(p1.ff), xv.push_back(p2.ff);
		yv.push_back(p1.ss), yv.push_back(p2.ss);
	}
	sort(xv.begin(), xv.end()), sort(yv.begin(), yv.end());
	xv.resize(int(unique(xv.begin(), xv.end()) - xv.begin()));
	yv.resize(int(unique(yv.begin(), yv.end()) - yv.begin()));	
	//pary(xv.begin(), xv.end());
	//pary(yv.begin(), yv.end());
	int xs = xv.size(), ys = yv.size();
	for (int i = 0;i < xs;i++) {
		vector<pii> ac(ys, {0, 0});
		vector<ll> dc(ys, 0);
		cost.push_back(ac), dp.push_back(dc);
	}
	for (int i = 0;i < n;i++) {
		int sx = lower_bound(xv.begin(), xv.end(), arr[i].st.ff) - xv.begin();
		int tx = lower_bound(xv.begin(), xv.end(), arr[i].ed.ff) - xv.begin();
		int sy = lower_bound(yv.begin(), yv.end(), arr[i].st.ss) - yv.begin();
		int ty = lower_bound(yv.begin(), yv.end(), arr[i].ed.ss) - yv.begin();
		if (sx == tx) {
			for (int j = sy;j < ty;j++) cost[sx][j].ss = max(cost[sx][j].ss, arr[i].cost);	
		} else {
			for (int j = sx;j < tx;j++) cost[j][sy].ff = max(cost[j][sy].ff, arr[i].cost);	
		}
	}
	for (int i = xs - 1;i >= 0;i--) {
		for (int j = ys - 1;j >= 0;j--) {
			dp[i][j] = max((i < xs - 1 ? dp[i + 1][j] + (xv[i + 1] - xv[i]) * cost[i][j].ff : 0), 
					(j < ys - 1 ? dp[i][j + 1] + (yv[j + 1] - yv[j]) * cost[i][j].ss : 0));
		}
	}
	
	while (q--) {
		pii p;
		cin >> p.ff >> p.ss;
		p = turn(p);
		int x = lower_bound(xv.begin(), xv.end(), p.ff) - xv.begin();
		int y = lower_bound(yv.begin(), yv.end(), p.ss) - yv.begin();
		//debug(x, y);
		ll ans = 0;
		if (x < xs) {
			for (int i = y;i < ys;i++) {
				ans = max(ans, dp[x][i] + (x ? (xv[x] - p.ff) * cost[x-1][i].ff : 0));
			}
		}
		if (y < ys) {
			for (int i = x;i < xs;i++) {
				ans = max(ans, dp[i][y] + (y ? (yv[y] - p.ss) * cost[i][y-1].ss : 0));
			}
		}	
		cout << ans << "\n";
		//debug();
	}
}
/*

2 2
1 2 1 4
3 1 3 2
1 2
3 3




*/

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