#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 2810;
const int M = N * 2;
const ll inf = (ll)1e18;
ll X[N], Y[N];
ll XX[N], YY[N];
ll val[N];
vector<ll> xc, yc;
ll XI[M][M];
ll YI[M][M];
ll dp[M][M];
const int Q = (int)3e6 + 10;
struct query{
ll xcor;
ll ycor;
int idx;
};
vector<query> qq[M][M];
ll outp[Q];
struct line{
ll ai;
ll bi;
ll lim;
};
ll divv(ll x, ll y){
return (x / y - (x%y != 0 && (x^y) < 0));
}
ll inter(line p1, line p2){
return divv(p1.bi - p2.bi, p2.ai - p1.ai);
}
struct hull{
vector<line> st;
void add_line(line qq){
while(!st.empty() && qq.ai >= st.back().ai)
st.pop_back();
// assume qq.ai < las.ai
ll p1, p2;
while(st.size() >= 2){
p1 = inter(st[st.size() - 1], qq);
p2 = inter(st[st.size() - 2], qq);
if(p1 < p2)
break;
st.pop_back();
}
if(st.size() > 0)
st[st.size() - 1].lim = inter(st[st.size() - 1], qq);
qq.lim = -(ll)1e18;
st.push_back(qq);
}
ll bins(ll pp){
int lf = 0;
int rf = st.size();
int mid;
while(lf < rf){
mid = (lf + rf) / 2;
if(st[mid].lim <= pp){
rf = mid;
}
else{
lf = mid + 1;
}
}
return st[lf].ai * 1ll * pp + st[lf].bi;
}
};
int main(){
fastIO;
int n, q;
cin >> n >> q;
ll start, en, tim;
for(int i = 1; i <= n; i ++ ){
cin >> tim >> start >> en >> val[i];
start *= 2ll;
tim *= 2ll;
en *= 2ll;
X[i] = tim + start;
Y[i] = tim - start;
tim += abs(en - start);
XX[i] = tim + en;
YY[i] = tim - en;
xc.push_back(X[i]);
yc.push_back(Y[i]);
xc.push_back(XX[i]);
yc.push_back(YY[i]);
}
sort(xc.begin(), xc.end());
sort(yc.begin(), yc.end());
xc.resize(unique(xc.begin(), xc.end()) - xc.begin());
yc.resize(unique(yc.begin(), yc.end()) - yc.begin());
int nn = xc.size();
int mm = yc.size();
int iq;
for(int i = 1; i <= n; i ++ ){
X[i] = lower_bound(xc.begin(), xc.end(), X[i]) - xc.begin();
Y[i] = lower_bound(yc.begin(), yc.end(), Y[i]) - yc.begin();
XX[i]= lower_bound(xc.begin(), xc.end(), XX[i]) - xc.begin();
YY[i] = lower_bound(yc.begin(), yc.end(), YY[i]) - yc.begin();
if(X[i] == XX[i]){
for(int j = Y[i] + 1; j <= YY[i]; j ++ ){
YI[X[i]][j] = max(YI[X[i]][j], val[i]);
}
}
else{
for(int j = X[i] + 1; j <= XX[i]; j ++ ){
XI[j][Y[i]] = max(XI[j][Y[i]], val[i]);
}
}
}
for(int x = nn - 1; x >= 0 ; x -- ){
for(int y = mm - 1; y >= 0; y -- ){
if(x + 1 < nn)
dp[x][y] = max(dp[x][y], dp[x + 1][y] + (xc[x + 1] - xc[x]) * 1ll * XI[x + 1][y]);
if(y + 1 < mm)
dp[x][y] = max(dp[x][y], dp[x][y + 1] + (yc[y + 1] - yc[y]) * 1ll * YI[x][y + 1]);
}
}
ll xa, ya;
int xlow, ylow;
ll big;
ll cc;
for(int iq = 1; iq <= q; iq ++ ){
cin >> tim >> start;
tim *= 2ll;
start *= 2ll;
xa = tim + start;
ya = tim - start;
xlow = lower_bound(xc.begin(), xc.end(), xa) - xc.begin();
ylow = lower_bound(yc.begin(), yc.end(), ya) - yc.begin();
if(xlow == nn || ylow == mm){
outp[iq] = 0;
continue;
}
qq[xlow][ylow].push_back({xa, ya, iq});
big = 0;
/*
for(int j = xlow; j < nn; j ++ ){
big = max(big, dp[j][ylow] + (yc[ylow] - ya) * 1ll * YI[j][ylow]);
}
for(int j = ylow; j < mm ; j ++ ){
big = max(big, dp[xlow][j] + (xc[xlow] - xa) * 1ll * XI[xlow][j]);
}
*/
}
for(int qy = 0; qy < mm; qy ++ ){
hull ash;
for(int qx = nn - 1; qx >= 0; qx -- ){
ash.add_line({YI[qx][qy],dp[qx][qy],-(ll)1e18});
for(auto xx : qq[qx][qy]){
outp[xx.idx] = max(outp[xx.idx], ash.bins(yc[qy] - xx.ycor));
}
}
}
for(int qx = 0; qx < nn; qx ++ ){
hull ash;
for(int qy = mm - 1; qy >= 0; qy -- ){
ash.add_line({XI[qx][qy], dp[qx][qy], -(ll)1e18});
for(auto xx : qq[qx][qy]){
outp[xx.idx] = max(outp[xx.idx], ash.bins(xc[qx] - xx.xcor));
}
}
}
for(int iq = 1; iq <= q; iq ++ ){
cout << outp[iq]/4ll << "\n";
}
return 0;
}
Compilation message
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:113:9: warning: unused variable 'iq' [-Wunused-variable]
113 | int iq;
| ^~
bodyguard.cpp:140:8: warning: variable 'big' set but not used [-Wunused-but-set-variable]
140 | ll big;
| ^~~
bodyguard.cpp:141:8: warning: unused variable 'cc' [-Wunused-variable]
141 | ll cc;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5203 ms |
1086812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2302 ms |
1044492 KB |
Output is correct |
| 2 |
Correct |
2298 ms |
1043668 KB |
Output is correct |
| 3 |
Incorrect |
2323 ms |
1047548 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2302 ms |
1044492 KB |
Output is correct |
| 2 |
Correct |
2298 ms |
1043668 KB |
Output is correct |
| 3 |
Incorrect |
2323 ms |
1047548 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2302 ms |
1044492 KB |
Output is correct |
| 2 |
Correct |
2298 ms |
1043668 KB |
Output is correct |
| 3 |
Incorrect |
2323 ms |
1047548 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5203 ms |
1086812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
