| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 595799 |
2022-07-14T07:04:44 Z |
반딧불(#8442) |
Bodyguard (JOI21_bodyguard) |
C++17 |
|
3651 ms |
360092 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e12;
int n, q, W, H;
ll sx[3002], sy[3002], ex[3002], ey[3002], w[3002];
ll qx[3000002], qy[3000002];
ll qcx[3000002], qcy[3000002];
ll wx[6004][6004], wy[6004][6004]; /// x�� �ٲ� / y�� �ٲ�
ll dist[6004][6004];
vector<ll> xVec, yVec;
ll ans[3000002];
void input();
void operate();
void output();
int main(){
input();
operate();
output();
}
void input(){
scanf("%d %d", &n, &q);
for(int i=1; i<=n; i++){
ll pt, pa, pb, pc, pl;
scanf("%lld %lld %lld %lld", &pt, &pa, &pb, &pc);
pt*=2, pa*=2, pb*=2, pc/=2;
pl = pt+abs(pa-pb);
sx[i] = (pt+pa)/2, sy[i] = (pt-pa)/2;
ex[i] = (pl+pb)/2, ey[i] = (pl-pb)/2;
w[i] = pc;
}
for(int i=1; i<=q; i++){
ll pt, px;
scanf("%lld %lld", &pt, &px);
pt*=2, px*=2;
qx[i] = (pt+px)/2, qy[i] = (pt-px)/2;
}
}
void renumber(){
xVec = yVec = vector<ll> (1, LLONG_MIN);
for(int i=1; i<=n; i++){
xVec.push_back(sx[i]), xVec.push_back(ex[i]);
yVec.push_back(sy[i]), yVec.push_back(ey[i]);
}
sort(xVec.begin(), xVec.end()); xVec.erase(unique(xVec.begin(), xVec.end()), xVec.end());
sort(yVec.begin(), yVec.end()); yVec.erase(unique(yVec.begin(), yVec.end()), yVec.end());
for(int i=1; i<=n; i++){
sx[i] = lower_bound(xVec.begin(), xVec.end(), sx[i]) - xVec.begin();
sy[i] = lower_bound(yVec.begin(), yVec.end(), sy[i]) - yVec.begin();
ex[i] = lower_bound(xVec.begin(), xVec.end(), ex[i]) - xVec.begin();
ey[i] = lower_bound(yVec.begin(), yVec.end(), ey[i]) - yVec.begin();
// printf("arr[i]: %lld %lld %lld %lld %lld\n", sx[i], sy[i], ex[i], ey[i], w[i]);
}
W = (int)xVec.size(), H = (int)yVec.size();
}
void makeEdges(){
for(int i=1; i<=n; i++){
if(sx[i] == ex[i]){
for(int y=sy[i]+1; y<=ey[i]; y++)
wy[sx[i]][y] = max(wy[sx[i]][y], w[i] * (yVec[y] - yVec[y-1]));
}
else{
for(int x=sx[i]+1; x<=ex[i]; x++)
wx[x][sy[i]] = max(wx[x][sy[i]], w[i] * (xVec[x] - xVec[x-1]));
}
}
}
void findDist(){
for(int x=W; x>0; x--){
for(int y=H; y>0; y--){
// printf("Dist %d %d: %lld\n", x, y, dist[x][y]);
dist[x-1][y] = max(dist[x-1][y], dist[x][y] + wx[x][y]);
dist[x][y-1] = max(dist[x][y-1], dist[x][y] + wy[x][y]);
}
}
for(int i=1; i<=q; i++){
qcx[i] = lower_bound(xVec.begin(), xVec.end(), qx[i]) - xVec.begin();
qcy[i] = lower_bound(yVec.begin(), yVec.end(), qy[i]) - yVec.begin();
ans[i] = dist[qcx[i]][qcy[i]];
}
}
struct Line{
ll a, b;
Line(){}
Line(ll a, ll b): a(a), b(b){}
ll get(ll x){
return a*x+b;
}
};
struct Node{
Node *lc, *rc;
ll s, e;
Line d = Line(0, -INF);
Node(){
s = e = 0, lc = rc = nullptr;
}
Node(ll s, ll e): s(s), e(e){
lc = rc = nullptr;
}
~Node(){
if(lc) delete lc;
if(rc) delete rc;
}
void addLine(Line x){
ll m = (s+e+INF+INF)/2-INF;
if(d.get(m) < x.get(m)) swap(x, d);
if(d.get(s) >= x.get(s) && d.get(e) >= x.get(e)) return;
if(d.get(s) < x.get(s)){
if(!lc) lc = new Node(s, m);
lc->addLine(x);
}
else{
if(!rc) rc = new Node(m+1, e);
rc->addLine(x);
}
}
ll query(ll x){
ll m = (s+e+INF+INF)/2-INF;
ll ret = d.get(x);
if(x<=m && lc) ret = max(ret, lc->query(x));
if(m<x && rc) ret = max(ret, rc->query(x));
return ret;
}
};
struct LiChao{
Node* root;
void init(){
if(root) delete root;
root = new Node(-INF, INF);
}
void addLine(Line x){
root->addLine(x);
}
ll query(ll x){
return root->query(x);
}
} tree;
vector<ll> xqVec[6002];
void findAnsX(){ /// x�� �������δ� ������ �ְ�, y�� �������� ���� ���� ���� �� ���ϱ�
for(int i=0; i<=W; i++) xqVec[i].clear();
for(int i=1; i<=q; i++) xqVec[qcx[i]].push_back(i);
for(int x=1; x<=W; x++){ /// [x-1, x] ������ �����ؾ� ��
vector<pair<ll, int> > vec; /// ��: ���, ��: ����
for(int i=1; i<=n; i++){
if(x <= sx[i] || ex[i] <= x-1) continue;
vec.push_back(make_pair(yVec[sy[i]], i));
}
for(auto key: xqVec[x]) vec.push_back(make_pair(qy[key], -key));
sort(vec.rbegin(), vec.rend());
tree.init();
for(pair<ll, int> p: vec){
if(p.second > 0){ /// �� �߰�
int px = p.second;
ll pa = -w[px], pb = dist[x][sy[px]] - pa * xVec[x];
tree.addLine(Line(pa, pb));
}
else{ /// �� ����
int px = -p.second;
ans[px] = max(ans[px], tree.query(qx[px]));
}
}
}
}
void flipAxis(){
swap(H, W);
swap(xVec, yVec);
for(int i=1; i<=n; i++) swap(sx[i], sy[i]), swap(ex[i], ey[i]);
for(int i=1; i<=q; i++) swap(qx[i], qy[i]), swap(qcx[i], qcy[i]);
for(int i=0; i<=H || i<=W; i++) for(int j=i+1; j<=H || j<=W; j++) swap(dist[i][j], dist[j][i]);
}
void operate(){
renumber();
makeEdges();
findDist();
findAnsX();
flipAxis();
findAnsX();
}
void output(){
for(int i=1; i<=q; i++){
printf("%lld\n", ans[i]);
}
}
Compilation message
bodyguard.cpp: In function 'void input()':
bodyguard.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
bodyguard.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | scanf("%lld %lld %lld %lld", &pt, &pa, &pb, &pc);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf("%lld %lld", &pt, &px);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3651 ms |
360092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
841 ms |
303888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
841 ms |
303888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
841 ms |
303888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3651 ms |
360092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
