| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 529534 |
2022-02-23T06:09:36 Z |
blue |
Bodyguard (JOI21_bodyguard) |
C++17 |
|
4217 ms |
1154200 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>
#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>;
#define sz(x) int(x.size())
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 lct
// {
// ll l;
// ll r;
// bool good;
// ll a;
// ll b;
// // int ii, jj;
// lct* left = NULL;
// lct* right = NULL;
// lct(vll& xv, ll i, ll j)
// {
// // ii = i, jj = j;
// l = xv[i];
// r = xv[j];
// good = 1;
// a = b = 0;
// if(i == j)
// {
// left = right = NULL;
// }
// else
// {
// left = new lct(xv, i, (i+j)/2);
// right = new lct(xv, (i+j)/2+1, j);
// }
// }
// // lct()
// // {
// // l = 0;
// // r = 2'000'000'000LL;
// // good = 1;
// // a = b = 0;
// // left = right = NULL;
// // }
// // lct(ll l1, ll r1, bool good1, ll a1, ll b1, lct* left1, lct* right1)
// // {
// // l = l1;
// // r = r1;
// // good = good1;
// // a = a1;
// // b = b1;
// // left = left1;
// // right = right1;
// // }
// void insert(ll na, ll nb)
// {
// if(na * l + nb <= a * l + b && na * r + nb <= a * r + b) return;
// // cerr << "inserting " << na << ' ' << nb << " into " << l << ' ' << r << '\n';
// if(na * l + nb >= a * l + b && na * r + nb >= a * r + b)
// {
// a = na;
// b = nb;
// good = 1;
// // cerr << "setting " << l << ' ' << r << " to " << na <<' ' << nb << '\n';
// }
// else
// {
// // cerr << "else : " << (left == NULL) << ' ' << (right == NULL) << ' ' << l << ' ' << r << '\n';
// // cerr << ii << ' ' << jj << '\n';
// // if(left == NULL)
// // {
// // left = new lct{l, (l+r)/2, 1, 0, 0, NULL, NULL};
// // }
// if(good)
// left->insert(a, b);
// left->insert(na, nb);
// // if(right == NULL)
// // {
// // right = new lct{(l+r)/2+1, r, 1, 0, 0, NULL, NULL};
// // }
// if(good)
// right->insert(a, b);
// right->insert(na, nb);
// good = 0;
// }
// }
// ll query(ll x)
// {
// if(good) return a * x + b;
// else if(x <= left->r) return left->query(x);
// else return right->query(x);
// }
// };
struct lct
{
vll xv;
vector<bool> good;
vector<ll> a;
vector<ll> b;
lct(vll& xv_)
{
xv = xv_;
good = vector<bool>((sz(xv) << 2) + 5, 0);
a = b = vector<ll>((sz(xv) << 2) + 5, 0);
good[1] = 1;
}
void insert(ll na, ll nb, int i, int xi, int xj)
{
if(na * xv[xi] + nb <= a[i] * xv[xi] + b[i] && na * xv[xj] + nb <= a[i] * xv[xj] + b[i]) return;
if(na * xv[xi] + nb >= a[i] * xv[xi] + b[i] && na * xv[xj] + nb >= a[i] * xv[xj] + b[i])
{
a[i] = na;
b[i] = nb;
good[i] = 1;
// cerr << "setting " << l << ' ' << r << " to " << na <<' ' << nb << '\n';
}
else
{
// cerr << "else : " << (left == NULL) << ' ' << (right == NULL) << ' ' << l << ' ' << r << '\n';
// cerr << ii << ' ' << jj << '\n';
// if(left == NULL)
// {
// left = new lct{l, (l+r)/2, 1, 0, 0, NULL, NULL};
// }
if(good[i])
insert(a[i], b[i], 2*i, xi, (xi+xj)/2);
insert(na, nb, 2*i, xi, (xi+xj)/2);
// if(right == NULL)
// {
// right = new lct{(l+r)/2+1, r, 1, 0, 0, NULL, NULL};
// }
if(good[i])
insert(a[i], b[i], 2*i+1, (xi+xj)/2, xj);
// right->insert(na, nb);
insert(na, nb, 2*i+1, (xi+xj)/2+1, xj);
// good = 0;
good[i] = 1;
}
}
void insert(ll na, ll nb)
{
insert(na, nb, 1, 0, sz(xv) - 1);
}
ll query(ll x, int i, int xi, int xj)
{
if(good[i]) return a[i] * x + b[i];
else if(x <= xv[(xi+xj)/2]) return query(x, 2*i, xi, (xi+xj)/2);
else return query(x, 2*i+1, (xi+xj)/2+1, xj);
}
ll query(ll x)
{
return query(x, 1, 0, sz(xv) - 1);
}
};
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;
}
// if(Q > 40'000) assert(0);
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;
// cerr << "ypx : " << T[i]+A[i] << ' ' << (T[i] + abs(A[i] - B[i])) + B[i] << '\n';
// cerr << "ymx : " << T[i] - A[i] << ' ' << (T[i] + abs(A[i] - B[i])) - B[i] << '\n';
}
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] ];
}
}
}
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]);
// cerr << i << ' ' << j << " : " << dp[i][j] << '\n';
}
}
vll res(1 + Q, 0);
vi queries[1 + pct][1 + mct];
for(int j = 1; j <= Q; j++)
{
if(P[j] + X[j] > ypx.back()) continue;
if(P[j] - X[j] > ymx.back()) continue;
int plo = 1, phi = pct;
while(plo != phi)
{
int mid = (plo + phi)/2;
if(ypx[mid] < P[j] + X[j])
plo = mid+1;
else
phi = mid;
}
int mlo = 1, mhi = mct;
while(mlo != mhi)
{
int mid = (mlo + mhi)/2;
if(ymx[mid] < P[j] - X[j])
mlo = mid+1;
else
mhi = mid;
}
// cerr << plo << ' ' << mlo << " A \n";
queries[plo][mlo].push_back(j);
}
// cerr << "done\n";
for(int mi = 1; mi <= mct; mi++)
{
set<ll> xv;
for(int pi = pct; pi >= 1; pi--)
{
for(int qr : queries[pi][mi])
{
xv.insert((ymx[mi] - (P[qr] - X[qr]))/2);
}
}
vll xvv;
for(ll kv : xv) xvv.push_back(kv);
if(xvv.empty()) continue;
// lct CHT(xvv, 0, sz(xvv) - 1);
lct CHT(xvv);
for(int pi = pct; pi >= 1; pi--)
{
// cerr << "\n\n\n\n\n";
// if(mi == 3)
// cerr << pi << ' ' << mi << " : " << "insert line " << ' ' << horiz_basic[pi][mi - 1] << ' ' << dp[pi][mi] << '\n';
CHT.insert(horiz_basic[pi][mi - 1], dp[pi][mi]);
for(int qr : queries[pi][mi])
{
res[qr] = max(res[qr], CHT.query((ymx[mi] - (P[qr] - X[qr]))/2));
// cerr << " ! " << res[qr] << '\n';
// cerr << "query = " << qr << ' ' << pi << ' ' << mi << '\n';
// cerr << "YMX = " << ymx[mi] << " - " << (P[qr] - X[qr]) << '\n';
// cerr << (ymx[mi] - (P[qr] - X[qr]))/2 << '\n';
// cerr << "x = " << (ymx[mi] - (P[qr] - X[qr]))/2 << "\n";
}
}
}
// cerr << pct << " ; " << mct << '\n';
// for(int pi = 1; pi <= pct; pi++)
// {
// cerr << ypx[pi] << " : ";
// for(int mi = 1; mi <= mct; mi++)
// {
// cerr << dp[pi][mi] << ' ';
// }
// cerr << '\n';
// }
// cerr << "done 1\n";
for(int pi = 1; pi <= pct; pi++)
{
set<ll> xv;
for(int mi = mct; mi >= 1; mi--)
{
for(int qr : queries[pi][mi])
{
xv.insert((ypx[pi] - (P[qr] + X[qr]))/2);
}
}
vll xvv;
for(ll kv : xv) xvv.push_back(kv);
if(xvv.empty()) continue;
lct CHT(xvv);
for(int mi = mct; mi >= 1; mi--)
{
// cerr << "pi mi = " << pi << ' ' << mi << '\n';
CHT.insert(vert_basic[pi - 1][mi], dp[pi][mi]);
// cerr << "ins done\n";
for(int qr : queries[pi][mi])
{
// cerr << "query = " << qr << " : " << pi << ' ' << mi << '\n';
res[qr] = max(res[qr], CHT.query((ypx[pi] - (P[qr] + X[qr]))/2));
// cerr << " ! " << res[qr] << '\n';
// cerr << "query done\n";
}
// c
// cerr << "finished\n";
}
}
for(int j = 1; j <= Q; j++) cout << res[j] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4217 ms |
716676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
922 ms |
1154116 KB |
Output is correct |
| 2 |
Correct |
937 ms |
1154200 KB |
Output is correct |
| 3 |
Correct |
926 ms |
1138804 KB |
Output is correct |
| 4 |
Correct |
23 ms |
48332 KB |
Output is correct |
| 5 |
Correct |
959 ms |
1153948 KB |
Output is correct |
| 6 |
Correct |
908 ms |
1153992 KB |
Output is correct |
| 7 |
Correct |
976 ms |
1152604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
922 ms |
1154116 KB |
Output is correct |
| 2 |
Correct |
937 ms |
1154200 KB |
Output is correct |
| 3 |
Correct |
926 ms |
1138804 KB |
Output is correct |
| 4 |
Correct |
23 ms |
48332 KB |
Output is correct |
| 5 |
Correct |
959 ms |
1153948 KB |
Output is correct |
| 6 |
Correct |
908 ms |
1153992 KB |
Output is correct |
| 7 |
Correct |
976 ms |
1152604 KB |
Output is correct |
| 8 |
Incorrect |
1276 ms |
1154192 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
922 ms |
1154116 KB |
Output is correct |
| 2 |
Correct |
937 ms |
1154200 KB |
Output is correct |
| 3 |
Correct |
926 ms |
1138804 KB |
Output is correct |
| 4 |
Correct |
23 ms |
48332 KB |
Output is correct |
| 5 |
Correct |
959 ms |
1153948 KB |
Output is correct |
| 6 |
Correct |
908 ms |
1153992 KB |
Output is correct |
| 7 |
Correct |
976 ms |
1152604 KB |
Output is correct |
| 8 |
Incorrect |
1276 ms |
1154192 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4217 ms |
716676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
