| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 907935 |
2024-01-16T06:20:49 Z |
box |
Bodyguard (JOI21_bodyguard) |
C++17 |
|
5143 ms |
830032 KB |
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#define cerr if (0) cerr
#endif
#define ar array
#define sz(v) int(std::size(v))
#define all(v) std::begin(v), std::end(v)
typedef long long i64;
typedef vector<int> vi;
void maxi(i64 &a, i64 b) {
a = max(a, b);
}
const double INF = 1e18;
struct hull {
struct line {
i64 m, b; double bet = INF;
i64 f(i64 x) { return m*x+b; }
};
double isect(line u, line v) {
return double(u.b-v.b)/double(v.m-u.m);
}
vector<line> L;
void add(line l) {
if (sz(L) && end(L)[-1].m == l.m) {
if (end(L)[-1].b >= l.b) return;
L.pop_back();
}
while (sz(L) > 1 && isect(l, end(L)[-2]) > end(L)[-1].bet) L.pop_back();
l.bet = sz(L) ? isect(l, end(L)[-1]) : INF;
L.push_back(l);
// for (auto l : L) cerr << l.m << ' ' << l.b << " | ";
// cerr << endl;
}
i64 qry(i64 x) {
if (sz(L) == 0) return 0;
int low = 0, hi = sz(L)-1;
while (low < hi) {
int m = (low+hi)/2+1;
if (L.at(m).bet >= x) low = m;
else hi = m-1;
}
// cerr << "GOT " << low << " / " << sz(L) << endl;
return L.at(low).f(x);
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N, Q; cin >> N >> Q;
vector<ar<i64, 4>> segx, segy;
for (int i = 0; i < N; i++) {
i64 t, a, b, c; cin >> t >> a >> b >> c;
c /= 2;
if (a > b) segy.push_back({t+a, t-a, t-2*b+a, c});
else segx.push_back({t-a, t+a, t+2*b-a, c});
}
vector<i64> X, Y;
for (auto [y, x1, x2, c] : segx) {
Y.push_back(y);
X.push_back(x1);
X.push_back(x2);
}
for (auto [x, y1, y2, c] : segy) {
X.push_back(x);
Y.push_back(y1);
Y.push_back(y2);
}
sort(all(X)), sort(all(Y));
X.erase(unique(all(X)), end(X)), Y.erase(unique(all(Y)), end(Y));
vector cx(sz(X), vector<i64>(sz(Y))), cy(sz(X), vector<i64>(sz(Y)));
for (auto [y, x1, x2, c] : segx) {
int a = lower_bound(all(Y), y) - begin(Y);
int bl = lower_bound(all(X), x1) - begin(X);
int br = lower_bound(all(X), x2) - begin(X);
for (int i = bl; i < br; i++) maxi(cx.at(i).at(a), c);
}
for (auto [x, y1, y2, c] : segy) {
int a = lower_bound(all(X), x) - begin(X);
int bl = lower_bound(all(Y), y1) - begin(Y);
int br = lower_bound(all(Y), y2) - begin(Y);
for (int i = bl; i < br; i++) maxi(cy.at(a).at(i), c);
}
vector dp(sz(X), vector<i64>(sz(Y)));
for (int i = sz(X)-1; i >= 0; i--) for (int j = sz(Y)-1; j >= 0; j--) {
if (i+1 < sz(X)) maxi(dp.at(i).at(j), dp.at(i+1).at(j) + cx.at(i).at(j)*(X.at(i+1)-X.at(i)));
if (j+1 < sz(Y)) maxi(dp.at(i).at(j), dp.at(i).at(j+1) + cy.at(i).at(j)*(Y.at(j+1)-Y.at(j)));
}
vector qry(sz(X), vector<vector<tuple<int, i64, i64>>>(sz(Y)));
vector<i64> ans(Q);
for (int i = 0; i < Q; i++) {
i64 p, a; cin >> p >> a;
i64 x = p+a, y = p-a;
int xp = lower_bound(all(X), x) - begin(X);
int yp = lower_bound(all(Y), y) - begin(Y);
if (xp == sz(X) || yp == sz(Y)) continue;
qry.at(xp).at(yp).push_back({i,x,y});
}
for (int i = sz(X)-1; i >= 0; i--) {
hull T;
for (int j = sz(Y)-1; j >= 0; j--) {
T.add({i?cx.at(i-1).at(j):0, dp.at(i).at(j)});
for (auto [p,x,y] : qry.at(i).at(j)) maxi(ans.at(p), T.qry(X.at(i)-x));
}
}
for (int j = sz(Y)-1; j >= 0; j--) {
hull T;
for (int i = sz(X)-1; i >= 0; i--) {
T.add({j?cy.at(i).at(j-1):0, dp.at(i).at(j)});
for (auto [p,x,y] : qry.at(i).at(j)) maxi(ans.at(p), T.qry(Y.at(j)-y));
}
}
for (auto v : ans) cout << v << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5143 ms |
569456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2498 ms |
829928 KB |
Output is correct |
| 2 |
Incorrect |
2423 ms |
830032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2498 ms |
829928 KB |
Output is correct |
| 2 |
Incorrect |
2423 ms |
830032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2498 ms |
829928 KB |
Output is correct |
| 2 |
Incorrect |
2423 ms |
830032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5143 ms |
569456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
