| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1216466 | PenguinsAreCute | Bodyguard (JOI21_bodyguard) | C++17 | 0 ms | 0 KiB |
#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";
}