#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;
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];
int main(){
fastIO;
freopen("in.txt","r",stdin);
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;
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){
cout << "0\n";
continue;
}
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]);
}
cout << big/4ll << "\n";
}
return 0;
}
Compilation message
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:52:9: warning: unused variable 'iq' [-Wunused-variable]
52 | int iq;
| ^~
bodyguard.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
26 | freopen("in.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
37 ms |
680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
