Submission #458283

#	Time	Username	Problem	Language	Result	Execution time	Memory
458283		8e7	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	4729 ms	662196 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 6005
#define maxq 3000005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
//#define __int128 long long
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;

struct query{
	ll x, y, ans;
	int xi, yi;
	query() {x = y = ans = 0, xi = yi = 0;};
	query(ll px, ll py) {
		x = px, y = py, ans = 0;
		xi = lower_bound(xv.begin(), xv.end(), x) - xv.begin();
		yi = lower_bound(yv.begin(), yv.end(), y) - yv.begin();
	}
} que[maxq];

vector<int> ix[maxn], iy[maxn];
struct convexhull{
	struct line{
		ll a, b;
		line() {a = 0, b = 0;};
		line(ll c, ll d) {a = c, b = d;};
		ll calc(ll x) {return a * x + b;}
	};
	vector<line> v; //slope is decreasing
	void ins(ll la, ll lb) {
		line cur = line(la, lb);
		while (v.size() && v.back().a <= cur.a) v.pop_back();
		while (v.size() >= 2) {
			line p2 = v.back(), p3 = *(v.rbegin() + 1);
			if ((__int128)(p2.b - p3.b) * (p3.a - cur.a) <= (__int128)(cur.b - p3.b) * (p3.a - p2.a)) {
				v.pop_back();
			} else {
				break;
			}
		}
		if (v.empty() || (cur.b > v.back().b)) v.push_back(cur);
	}
	ll getval(ll x) {
		int low = -1, up = v.size();
		while (low < up - 1) {
			int mid = (low + up) / 2;
			ll v1 = v[mid].calc(x), v2 = (mid + 1 < v.size() ? v[mid + 1].calc(x) : -(1LL<<60)); 
			if (v2 - v1 < 0) up = mid;
			else low = mid;
		}
		return max(low >= 0 ? v[low].calc(x) : 0, up < v.size() ? v[up].calc(x) : 0);
	}
};
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));
		}
	}
		
	for (int i = 0;i < q;i++) {
		pii p;
		cin >> p.ff >> p.ss;
		p = turn(p);
		que[i] = query(p.ff, p.ss);
		ix[que[i].xi].push_back(i);	
		iy[que[i].yi].push_back(i);
		/*
		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";
		*/
	}
	for (int i = 0;i < xs;i++) sort(ix[i].begin(), ix[i].end(), [&](int x, int y) {return que[x].yi > que[y].yi;});
	for (int i = 0;i < ys;i++) sort(iy[i].begin(), iy[i].end(), [&](int x, int y) {return que[x].xi > que[y].xi;});
	for (int i = 0;i < xs;i++) {
		convexhull hull;
		int ind = 0;
		for (int j = ys - 1;j >= 0;j--) {
			hull.ins((i ? cost[i-1][j].ff : 0), dp[i][j]);
			while (ind < ix[i].size() && que[ix[i][ind]].yi >= j) {
				int cur = ix[i][ind];
				ind++;
				if (que[cur].yi > j) continue;
				//debug(i, j, cur, hull.getval(xv[i] - que[cur].x));
				que[cur].ans = max(que[cur].ans, hull.getval(xv[i] - que[cur].x));
			}
		}
	}	
	for (int j = 0;j < ys;j++) {
		convexhull hull;
		int ind = 0;
		for (int i = xs - 1;i >= 0;i--) {
			hull.ins((j ? cost[i][j-1].ss : 0), dp[i][j]);
			while (ind < iy[j].size() && que[iy[j][ind]].xi >= i) {
				int cur = iy[j][ind];
				ind++;
				if (que[cur].xi > i) continue;
				que[cur].ans = max(que[cur].ans, hull.getval(yv[j] - que[cur].y));
			}
		}
	}
	for (int i = 0;i < q;i++) cout << que[i].ans << "\n";
}

/*
 
2 2
1 2 1 4
3 1 3 2
1 2
3 3
 
 
 
 
*/

Compilation message (stderr)

bodyguard.cpp: In member function 'long long int convexhull::getval(long long int)':
bodyguard.cpp:74:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<convexhull::line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    ll v1 = v[mid].calc(x), v2 = (mid + 1 < v.size() ? v[mid + 1].calc(x) : -(1LL<<60));
      |                                  ~~~~~~~~^~~~~~~~~~
bodyguard.cpp:78:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<convexhull::line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   return max(low >= 0 ? v[low].calc(x) : 0, up < v.size() ? v[up].calc(x) : 0);
      |                                             ~~~^~~~~~~~~~
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:152:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |    while (ind < ix[i].size() && que[ix[i][ind]].yi >= j) {
      |           ~~~~^~~~~~~~~~~~~~
bodyguard.cpp:166:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |    while (ind < iy[j].size() && que[iy[j][ind]].xi >= i) {
      |           ~~~~^~~~~~~~~~~~~~

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