| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 458258 |
2021-08-08T03:25:23 Z |
8e7 |
Bodyguard (JOI21_bodyguard) |
C++17 |
|
3481 ms |
509824 KB |
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#define ll long long
#define maxn 6005
#define maxq 3000005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define __int128 long long
struct seg{
pii st, ed;
ll cost;
seg(){st = {0, 0}, ed = {0, 0}, cost = 0;}
seg(pii x, pii y, ll c){st = x, ed = y, cost = c;};
} arr[maxn];
vector<ll> xv, yv;
vector<vector<pii> > cost;
vector<vector<ll> > dp;
struct query{
ll x, y, ans;
int xi, yi;
query() {x = y = ans = 0, xi = yi = 0;};
query(ll px, ll py) {
x = px, y = py, ans = 0;
xi = lower_bound(xv.begin(), xv.end(), x) - xv.begin();
yi = lower_bound(yv.begin(), yv.end(), y) - yv.begin();
}
} que[maxq];
vector<int> ix[maxn], iy[maxn];
struct convexhull{
struct line{
ll a, b;
line() {a = 0, b = 0;};
line(ll c, ll d) {a = c, b = d;};
ll calc(ll x) {return a * x + b;}
};
vector<line> v; //slope is decreasing
void ins(ll la, ll lb) {
line cur = line(la, lb);
while (v.size() && v.back().a <= cur.a) v.pop_back();
while (v.size() > 2) {
line p2 = v.back(), p3 = *(v.rbegin() + 1);
if ((__int128)(p2.b - p3.b) * (p3.a - cur.a) <= (__int128)(cur.b - p3.b) * (p3.a - p2.a)) {
v.pop_back();
} else {
break;
}
}
v.push_back(cur);
}
ll getval(ll x) {
int low = -1, up = v.size();
while (low < up - 1) {
int mid = (low + up) / 2;
ll v1 = v[mid].calc(x), v2 = (mid + 1 < v.size() ? v[mid + 1].calc(x) : -(1LL<<60));
if (v2 - v1 < 0) up = mid;
else low = mid;
}
return max(low >= 0 ? v[low].calc(x) : 0, up < v.size() ? v[up].calc(x) : 0);
}
};
int main() {
io
int n, q;
cin >> n >> q;
auto turn = [&](pii p) {return make_pair((p.ff - p.ss), (p.ff + p.ss));};
for (int i = 0;i < n;i++) {
ll t, a, b, c;
cin >> t >> a >> b >> c;
pii p1 = {t, a}, p2 = {t + abs(b - a), b};
p1 = turn(p1), p2 = turn(p2);
arr[i] = seg(p1, p2, c / 2);
xv.push_back(p1.ff), xv.push_back(p2.ff);
yv.push_back(p1.ss), yv.push_back(p2.ss);
}
sort(xv.begin(), xv.end()), sort(yv.begin(), yv.end());
xv.resize(int(unique(xv.begin(), xv.end()) - xv.begin()));
yv.resize(int(unique(yv.begin(), yv.end()) - yv.begin()));
//pary(xv.begin(), xv.end());
//pary(yv.begin(), yv.end());
int xs = xv.size(), ys = yv.size();
for (int i = 0;i < xs;i++) {
vector<pii> ac(ys, {0, 0});
vector<ll> dc(ys, 0);
cost.push_back(ac), dp.push_back(dc);
}
for (int i = 0;i < n;i++) {
int sx = lower_bound(xv.begin(), xv.end(), arr[i].st.ff) - xv.begin();
int tx = lower_bound(xv.begin(), xv.end(), arr[i].ed.ff) - xv.begin();
int sy = lower_bound(yv.begin(), yv.end(), arr[i].st.ss) - yv.begin();
int ty = lower_bound(yv.begin(), yv.end(), arr[i].ed.ss) - yv.begin();
if (sx == tx) {
for (int j = sy;j < ty;j++) cost[sx][j].ss = max(cost[sx][j].ss, arr[i].cost);
} else {
for (int j = sx;j < tx;j++) cost[j][sy].ff = max(cost[j][sy].ff, arr[i].cost);
}
}
for (int i = xs - 1;i >= 0;i--) {
for (int j = ys - 1;j >= 0;j--) {
dp[i][j] = max((i < xs - 1 ? dp[i + 1][j] + (xv[i + 1] - xv[i]) * cost[i][j].ff : 0),
(j < ys - 1 ? dp[i][j + 1] + (yv[j + 1] - yv[j]) * cost[i][j].ss : 0));
}
}
for (int i = 0;i < q;i++) {
pii p;
cin >> p.ff >> p.ss;
p = turn(p);
que[i] = query(p.ff, p.ss);
ix[que[i].xi].push_back(i);
iy[que[i].yi].push_back(i);
/*
if (x < xs) {
for (int i = y;i < ys;i++) {
ans = max(ans, dp[x][i] + (x ? (xv[x] - p.ff) * cost[x-1][i].ff : 0));
}
}
if (y < ys) {
for (int i = x;i < xs;i++) {
ans = max(ans, dp[i][y] + (y ? (yv[y] - p.ss) * cost[i][y-1].ss : 0));
}
}
cout << ans << "\n";
*/
}
for (int i = 0;i < xs;i++) sort(ix[i].begin(), ix[i].end(), [&](int x, int y) {return que[x].yi > que[y].yi;});
for (int i = 0;i < ys;i++) sort(iy[i].begin(), iy[i].end(), [&](int x, int y) {return que[x].xi > que[y].xi;});
for (int i = 0;i < xs;i++) {
convexhull hull;
int ind = 0;
for (int j = ys - 1;j >= 0;j--) {
hull.ins((i ? cost[i-1][j].ff : 0), dp[i][j]);
while (ind < ix[i].size() && que[ix[i][ind]].yi >= j) {
int cur = ix[i][ind];
//debug(i, j, cur, hull.getval(xv[i] - que[cur].x));
que[cur].ans = max(que[cur].ans, hull.getval(xv[i] - que[cur].x));
ind++;
}
}
}
for (int j = 0;j < ys;j++) {
convexhull hull;
int ind = 0;
for (int i = xs - 1;i >= 0;i--) {
hull.ins((j ? cost[i][j-1].ss : 0), dp[i][j]);
while (ind < iy[j].size() && que[iy[j][ind]].xi >= i) {
int cur = iy[j][ind];
//debug(i, j, cur, hull.getval(yv[j] - que[cur].y));
que[cur].ans = max(que[cur].ans, hull.getval(yv[j] - que[cur].y));
ind++;
}
}
}
for (int i = 0;i < q;i++) cout << que[i].ans << "\n";
}
/*
2 2
1 2 1 4
3 1 3 2
1 2
3 3
*/
Compilation message
bodyguard.cpp: In member function 'long long int convexhull::getval(long long int)':
bodyguard.cpp:74:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<convexhull::line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | ll v1 = v[mid].calc(x), v2 = (mid + 1 < v.size() ? v[mid + 1].calc(x) : -(1LL<<60));
| ~~~~~~~~^~~~~~~~~~
bodyguard.cpp:78:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<convexhull::line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | return max(low >= 0 ? v[low].calc(x) : 0, up < v.size() ? v[up].calc(x) : 0);
| ~~~^~~~~~~~~~
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:152:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | while (ind < ix[i].size() && que[ix[i][ind]].yi >= j) {
| ~~~~^~~~~~~~~~~~~~
bodyguard.cpp:165:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | while (ind < iy[j].size() && que[iy[j][ind]].xi >= i) {
| ~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3481 ms |
379388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1207 ms |
509824 KB |
Output is correct |
| 2 |
Incorrect |
1197 ms |
509796 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1207 ms |
509824 KB |
Output is correct |
| 2 |
Incorrect |
1197 ms |
509796 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1207 ms |
509824 KB |
Output is correct |
| 2 |
Incorrect |
1197 ms |
509796 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3481 ms |
379388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
