Submission #1216464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216464		PenguinsAreCute	Bodyguard (JOI21_bodyguard)	C++17	0 / 100	3864 ms	973908 KiB

bodyguard

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct line {
	int m;
	long long c;
	line(): m(0), c(-1e18) {}
	line(int _m, long long _c): m(_m), c(_c) {}
	long long operator [] (int x) {
		return 1LL * m * x + c;
	}
};
struct node {
	int s, e, m;
	line v;
	node *l, *r;
	node(int _s, int _e): s(_s), e(_e), m(_s+(_e-_s)/2), l(NULL), r(NULL) {}
	node(): s(-(1e9+5)), e(1e9+5), m(0), l(NULL), r(NULL) {}
	void create() {
		if(!l && e - s > 1) {
			l = new node(s, m);
			r = new node(m, e);
		}
	}
	void operator += (line x) {
		if(x[m] > v[m])
			swap(x, v);
		bool st = x[s] > v[s], nd = x[e] > v[e];
		if((!st && !nd) || e - s == 1 || (x.m == 0 && x.c == -1e18))
			return;
		create();
		if(st)
			(*l) += v;
		else
			(*r) += v;
	}
	long long operator [] (int x) {
		long long ans = v[x];
		if(!l || e - s == 1)
			return ans;
		if(x < m)
			return max(ans, (*l)[x]);
		return max(ans, (*r)[x]);
	}
};
signed main() {
	int n, q;
	cin >> n >> q;
	vector<long long> x1(n), y1(n), x2(n), y2(n), x, y;
	vector<int> c(n);
	for(int i=0;i<n;i++) {
		int t, a, b;
		cin >> t >> a >> b >> c[i];
		long long st = t, sx = a;
		long long et = t + abs(b - a), ex = b;
		x1[i] = st + sx;
		y1[i] = st - sx;
		x2[i] = et + ex;
		y2[i] = et - ex;
		x.push_back(x1[i]);
		x.push_back(x2[i]);
		y.push_back(y1[i]);
		y.push_back(y2[i]);
		c[i] /= 2;
	}
	sort(x.begin(),x.end());
	sort(y.begin(),y.end());
	long long dp[2*n][2*n], xdelta[2*n-1][2*n], ydelta[2*n][2*n-1];
	memset(xdelta,0,sizeof(xdelta));
	memset(ydelta,0,sizeof(ydelta));
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;i++) {
		x1[i] = lower_bound(x.begin(),x.end(),x1[i]) - x.begin();
		y1[i] = lower_bound(y.begin(),y.end(),y1[i]) - y.begin();
		x2[i] = lower_bound(x.begin(),x.end(),x2[i]) - x.begin();
		y2[i] = lower_bound(y.begin(),y.end(),y2[i]) - y.begin();
		assert(x1[i] == x2[i] || y1[i] == y2[i]);
		if(x1[i] == x2[i])
			for(int j=y1[i];j<y2[i];j++)
				ydelta[x1[i]][j] += c[i];
		else
			for(int j=x1[i];j<x2[i];j++)
				xdelta[j][y1[i]] += c[i];
	}
	for(int i=2*n;i--;)
		for(int j=2*n;j--;) {
			if(i<2*n-1)
				dp[i][j] = max(dp[i][j],dp[i+1][j]+xdelta[i][j]*(x[i+1]-x[i]));
			if(j<2*n-1)
				dp[i][j] = max(dp[i][j],dp[i][j+1]+ydelta[i][j]*(y[j+1]-y[j]));
		}
	int cx[q], cy[q];
	long long ans[q];
	vector<pair<int,int>> qx[2*n], qy[2*n];
	for(int i=0;i<q;i++) {
		int t, p;
		cin >> t >> p;
		cx[i] = t + p;
		cy[i] = t - p;
		int gx = lower_bound(x.begin(),x.end(),cx[i]) - x.begin();
		int gy = lower_bound(y.begin(),y.end(),cy[i]) - y.begin();
		if(gx >= 2*n && gy >= 2*n)
			ans[i] = 0;
		else {
			if(gx)
				qy[gx].push_back({gy,i});
			if(gy)
				qx[gy].push_back({gx,i});
			ans[i] = dp[gx][gy];
		}
		/*
		if(gx >= 2 * n || gy >= 2 * n)
			cout << "0\n";
		else {
			long long ans = dp[gx][gy];
			if(gx)
				for(int i=gy;i<2*n;i++)
					ans = max(ans,xdelta[gx-1][i] / (x[gx]-x[gx-1]) * (x[gx] - cx) + dp[gx][i]);
			if(gy)
				for(int i=gx;i<2*n;i++)
					ans = max(ans,ydelta[i][gy-1] / (y[gy]-y[gy-1]) * (y[gy] - cy) + dp[i][gy]);
			cout << ans << "\n";
		}
		*/
	}
	for(int i=1;i<2*n;i++) {
		sort(qy[i].begin(),qy[i].end(),greater<pair<int,int>>());
		node lichao;
		int ptr = 2 * n;
		for(auto [t, idx]: qy[i]) {
			while(ptr > t) {
				ptr--;
				lichao += line(-(xdelta[i-1][ptr]),dp[i][ptr]+xdelta[i-1][ptr]*x[i]);
			}
			ans[idx] = max(ans[idx], lichao[cx[idx]]);
		}
	}
	for(int i=1;i<2*n;i++) {
		sort(qx[i].begin(),qx[i].end(),greater<pair<int,int>>());
		node lichao;
		int ptr = 2 * n;
		for(auto [t, idx]: qx[i]) {
			while(ptr > t) {
				ptr--;
				lichao += line(-(ydelta[ptr][i-1]),dp[ptr][i]+ydelta[ptr][i-1]*y[i]);
			}
			ans[idx] = max(ans[idx], lichao[cy[idx]]);
		}
	}
	for(int i=0;i<q;i++)
		cout << ans[i] << "\n";
}

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