| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 529228 |
2022-02-22T13:47:25 Z |
blue |
Bodyguard (JOI21_bodyguard) |
C++17 |
|
25000 ms |
740400 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
using vvi = vector<vi>;
const int maxN = 2'800;
int N;
vll T(1 + maxN), A(1 + maxN), B(1 + maxN), C(1 + maxN);
const int maxQ = 3'000'000;
int Q;
vll P(1 + maxQ), X(1 + maxQ);
const ll INF = 1'000'000'000'000'000'000LL;
struct slope_line
{
double e;
ll a;
ll b;
};
bool operator < (slope_line A, slope_line B)
{
return A.a < B.a;
}
struct point_line
{
double e;
ll a;
ll b;
};
bool operator < (point_line A, point_line B)
{
return A.e < B.e;
}
double get_intersect(ll a1, ll b1, ll a2, ll b2)
{
return double(b1 - b2) / double(a2 - a1);
}
bool good(ll a0, ll b0, ll a, ll b, ll a1, ll b1)
{
return double(b0 - b) / double(a - a0) < double(b - b1) / double(a1 - a);
}
struct cht
{
multiset<slope_line> sl;
multiset<point_line> pl;
ll query(ll x)
{
if(pl.empty()) return 0;
auto it = pl.lower_bound({double(x), 0, 0});
//
// cerr << it->a << ' ' << it->b << '\n';
// for(auto& plv : pl) cerr << plv.e << ' ' << plv.a << ' ' << plv.b << " ";
// cerr << '\n';
return it->a * x + it->b;
}
void insert(ll a, ll b)
{
// cerr << "inserting " << a << ' ' << b << '\n';
multiset<slope_line>::iterator it, nxt, prv, nxt2, prv2;
it = sl.lower_bound({-1, a, b});
if(it != sl.end() && it->a == a && it->b >= b) return;
// cerr << "check\n";
if(it != sl.end() && it->a == a)
{
pl.erase({it->e, it->a, it->b});
sl.erase(it);
}
sl.insert({-1, a, b});
// cerr << "hello\n";
//
it = sl.find({-1, a, b});
nxt = it;
nxt++;
// cerr << "why\n";
if(nxt != sl.end())
{
prv = it;
if(prv != sl.begin())
{
prv--;
ll a0 = prv->a, b0 = prv->b;
ll a1 = nxt->a, b1 = nxt->b;
/*
a0 * int0 + b0 == a * int0 + b
int0 = (b - b0) / (a0 - a)
= (b0 - b) / (a - a0)
int1 = (b1 - b) / (a - a1)
= (b - b1) / (a1 - a)
int0 < int1 => (b0 - )
*/
if(!good(a0, b0, a, b, a1, b1))
{
return;
}
// cerr << "passed\n";
}
}
// cerr << "cleared\n";
while(1)
{
nxt = sl.find({-1, a, b});
nxt++;
if(nxt == sl.end()) break;
nxt2 = nxt;
nxt2++;
if(nxt2 == sl.end()) break;
if(good(a, b, nxt->a, nxt->b, nxt2->a, nxt2->b)) break;
sl.erase(nxt);
pl.erase({nxt->e, nxt->a, nxt->b});
}
while(1)
{
prv = sl.find({-1, a, b});
if(prv == sl.begin()) break;
prv--;
prv2 = prv;
if(prv2 == sl.begin()) break;
prv2--;
if(good(prv2->a, prv2->b, prv->a, prv->b, a, b)) break;
ll prv2a = prv2->a;
ll prv2b = prv2->b;
double prv2e = get_intersect(a, b, prv2->a, prv2->b);
sl.erase(prv);
pl.erase({prv->e, prv->a, prv->b});
sl.erase(prv2);
pl.erase({prv2->e, prv2->a, prv2->b});
sl.insert({prv2e, prv2a, prv2b});
pl.insert({prv2e, prv2a, prv2b});
}
double endv, startv;
nxt = sl.find({-1, a, b});
nxt++;
if(nxt == sl.end()) endv = 2'000'000'005;
else
{
// cerr << "#\n";
// cerr << a << ' ' << b << " : " << nxt->a << ' ' << nxt->b << '\n';
endv = double(nxt->b - b) / double(a - nxt->a);
// cerr << endv << '\n';
}
// cerr << "endv = " << endv << '\n';
prv = sl.find({-1, a, b});
if(prv != sl.begin())
{
// cerr << "entered\n";
prv--;
startv = double(prv->b - b) / double(a - prv->a);
slope_line new_prev = {startv, prv->a, prv->b};
// cerr << "hello\n";
// cerr << "why\n";
// for(auto& plv : pl)
// {
// cerr << plv.e << ' ' << plv.a << ' ' << plv.b << " | ";
// }
// cerr << '\n';
// cerr << "nv = " << prv->e << ' ' << prv->a << ' ' << prv->b << '\n';
pl.erase({prv->e, prv->a, prv->b});
// cerr << "checking\n";
sl.erase(prv);
sl.insert(new_prev);
pl.insert({new_prev.e, new_prev.a, new_prev.b});
}
sl.erase({-1, a, b});
sl.insert({endv, a, b});
pl.insert({endv, a, b});
// cerr << "final line = " << endv << ' ' << a << ' ' << b << '\n';
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> Q;
for(int i = 1; i <= N; i++)
{
cin >> T[i] >> A[i] >> B[i] >> C[i];
T[i] *= 2;
A[i] *= 2;
B[i] *= 2;
C[i] /= 2;
}
for(int j = 1; j <= Q; j++)
{
cin >> P[j] >> X[j];
P[j] *= 2;
X[j] *= 2;
}
map<ll, ll> ypx_map, ymx_map;
for(int i = 1; i <= N; i++)
{
ypx_map[T[i] + A[i]] = 0;
ymx_map[T[i] - A[i]] = 0;
ypx_map[(T[i] + abs(A[i] - B[i])) + B[i]] = 0;
ymx_map[(T[i] + abs(A[i] - B[i])) - B[i]] = 0;
}
ll pct = 0, mct = 0;
vll ypx{-2'000'000'002LL};
vll ymx{-2'000'000'002LL};
for(auto& z : ypx_map)
{
z.second = ++pct;
ypx.push_back(z.first);
}
for(auto& z : ymx_map)
{
z.second = ++mct;
ymx.push_back(z.first);
}
vi start_ypx(1 + N), start_ymx(1 + N), end_ypx(1 + N), end_ymx(1 + N);
for(int i = 1; i <= N; i++)
{
start_ypx[i] = ypx_map[T[i] + A[i]];
start_ymx[i] = ymx_map[T[i] - A[i]];
end_ypx[i] = ypx_map[T[i] + abs(A[i] - B[i]) + B[i]];
end_ymx[i] = ymx_map[T[i] + abs(A[i] - B[i]) - B[i]];
}
//i = ypx, j = ymx
vvll horiz(1 + pct, vll(1 + mct, 0)); //(i, j) -> (i, j+1)
vvll vert(1 + pct, vll(1 + mct, 0)); //(i, j) - (i+1, j)
vvll horiz_basic(1 + pct, vll(1 + mct, 0)); //(i, j) -> (i, j+1)
vvll vert_basic(1 + pct, vll(1 + mct, 0)); //(i, j) - (i+1, j)
for(int i = 1; i <= N; i++)
{
if(B[i] < A[i])
{
for(int j = start_ymx[i]; j < end_ymx[i]; j++)
{
// cerr << start_ypx[i] << " ! " << j << '\n';
horiz_basic[ start_ypx[i] ][j] = max(horiz_basic[ start_ypx[i] ][j], C[i]);
// horiz[ start_ypx[i] ][j] = max(horiz[start_ypx[i]][j], (ymx[j+1] - ymx[j])/2 * C[i]);
horiz[start_ypx[i]][j] = horiz_basic[start_ypx[i]][j] * (ymx[j+1] - ymx[j]) / 2;
// cerr << ymx[j+1] << ' ' << ymx[j] << ' ' << C[i] << '\n';
// cerr << horiz[start_ypx[i]][j] << '\n';
}
}
else
{
for(int j = start_ypx[i]; j < end_ypx[i]; j++)
{
vert_basic[j][ start_ymx[i] ] = max(vert_basic[j][start_ymx[i]], C[i]);
vert[j][ start_ymx[i] ] = (ypx[j+1] - ypx[j])/2 * vert_basic[ j ][ start_ymx[i] ];
}
}
}
// cerr << "\n\n\n!!!\n";
// cerr << pct << ' ' << mct << '\n';
// for(int i = 1; i <= N; i++)
// {
// cerr << T[i] << ' ' << A[i] << ' ' << B[i] << ' ' << C[i] << '\n';
// }
// for(int i = 1; i <= pct; i++)
// {
// for(int j = 1; j <= mct; j++) cerr << horiz[i][j] << ' ';
// cerr << '\n';
// }
// cerr << "----\n";
// for(int i = 1; i <= pct; i++)
// {
// for(int j = 1; j <= mct; j++) cerr << vert[i][j] << ' ';
// cerr << '\n';
// }
vvll dp(1 + pct, vll(1 + mct, 0));
for(int i = pct; i >= 1; i--)
{
for(int j = mct; j >= 1; j--)
{
if(i < pct) dp[i][j] = max(dp[i][j], dp[i+1][j] + vert[i][j]);
if(j < mct) dp[i][j] = max(dp[i][j], dp[i][j+1] + horiz[i][j]);
}
}
// for(int i = 1; i <= pct; i++)
// {
// for(int j = 1; j <= mct; j++)
// {
// cerr << dp[i][j] << ' ';
// }
// cerr << '\n';
// }
for(int j = 1; j <= Q; j++)
{
ll res = 0;
if(P[j] + X[j] <= ypx.back())
{
if(P[j] - X[j] <= ymx.back())
{
int pi = 0, mi = 0;
while(ypx[pi] < P[j] + X[j])
pi++;
while(ymx[mi] < P[j] - X[j])
mi++;
cht pv;
for(int pi2 = pi; pi2 <= pct; pi2++)
{
res = max(res, dp[pi2][mi] + (ymx[mi] - (P[j] - X[j]))/2 * horiz_basic[pi2][mi - 1]);
// ymx[mi] * horiz_basic[pi2][mi-1] - (P)
// pv.insert(- horiz_basic[pi2][mi - 1], dp[pi2][mi] + (ymx[mi] * horiz_basic[pi2][mi - 1]));
pv.insert(horiz_basic[pi2][mi - 1], dp[pi2][mi]);
// cerr << "inserting line " <<
}
res = max(res, pv.query((ymx[mi] - (P[j] - X[j]))/2));
for(int mi2 = mi; mi2 <= mct; mi2++)
{
res = max(res, dp[pi][mi2] + (ypx[pi] - (P[j] + X[j]))/2 * vert_basic[pi - 1][mi2]);
}
}
}
cout << res << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
25047 ms |
388336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
449 ms |
739436 KB |
Output is correct |
| 2 |
Correct |
445 ms |
739560 KB |
Output is correct |
| 3 |
Correct |
417 ms |
730080 KB |
Output is correct |
| 4 |
Correct |
21 ms |
48076 KB |
Output is correct |
| 5 |
Correct |
480 ms |
739324 KB |
Output is correct |
| 6 |
Correct |
430 ms |
739396 KB |
Output is correct |
| 7 |
Correct |
497 ms |
738500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
449 ms |
739436 KB |
Output is correct |
| 2 |
Correct |
445 ms |
739560 KB |
Output is correct |
| 3 |
Correct |
417 ms |
730080 KB |
Output is correct |
| 4 |
Correct |
21 ms |
48076 KB |
Output is correct |
| 5 |
Correct |
480 ms |
739324 KB |
Output is correct |
| 6 |
Correct |
430 ms |
739396 KB |
Output is correct |
| 7 |
Correct |
497 ms |
738500 KB |
Output is correct |
| 8 |
Correct |
1297 ms |
739484 KB |
Output is correct |
| 9 |
Correct |
1317 ms |
739684 KB |
Output is correct |
| 10 |
Correct |
506 ms |
728676 KB |
Output is correct |
| 11 |
Correct |
28 ms |
48076 KB |
Output is correct |
| 12 |
Correct |
624 ms |
739436 KB |
Output is correct |
| 13 |
Correct |
2218 ms |
739596 KB |
Output is correct |
| 14 |
Correct |
817 ms |
739408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
449 ms |
739436 KB |
Output is correct |
| 2 |
Correct |
445 ms |
739560 KB |
Output is correct |
| 3 |
Correct |
417 ms |
730080 KB |
Output is correct |
| 4 |
Correct |
21 ms |
48076 KB |
Output is correct |
| 5 |
Correct |
480 ms |
739324 KB |
Output is correct |
| 6 |
Correct |
430 ms |
739396 KB |
Output is correct |
| 7 |
Correct |
497 ms |
738500 KB |
Output is correct |
| 8 |
Correct |
1297 ms |
739484 KB |
Output is correct |
| 9 |
Correct |
1317 ms |
739684 KB |
Output is correct |
| 10 |
Correct |
506 ms |
728676 KB |
Output is correct |
| 11 |
Correct |
28 ms |
48076 KB |
Output is correct |
| 12 |
Correct |
624 ms |
739436 KB |
Output is correct |
| 13 |
Correct |
2218 ms |
739596 KB |
Output is correct |
| 14 |
Correct |
817 ms |
739408 KB |
Output is correct |
| 15 |
Correct |
12390 ms |
740144 KB |
Output is correct |
| 16 |
Correct |
12097 ms |
740400 KB |
Output is correct |
| 17 |
Correct |
1925 ms |
731456 KB |
Output is correct |
| 18 |
Correct |
59 ms |
48324 KB |
Output is correct |
| 19 |
Correct |
2348 ms |
739884 KB |
Output is correct |
| 20 |
Correct |
24042 ms |
739992 KB |
Output is correct |
| 21 |
Correct |
4565 ms |
740120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
25047 ms |
388336 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
