Submission #596039

# Submission time Handle Problem Language Result Execution time Memory
596039 2022-07-14T09:28:39 Z 조영욱(#8444) Bodyguard (JOI21_bodyguard) C++17
0 / 100
3854 ms 322772 KB
#include <bits/stdc++.h>
using namespace std;

int n,q;
vector<long long> px;
vector<long long> py;
typedef pair<long long,long long> P;
typedef pair<P,P> PP;
typedef pair<PP,int> PPi;
vector<PPi> v;
int arr[5600][5600][2]; //0:x�� 1:y��
long long dp[5600][5600];

struct Node {
    P line;
    int l,r;
};

const long long INF=3e9+7;
vector<Node> seg;
Node emp={P(0,-INF*INF),-1,-1};

long long f(P a,long long x) {
    return a.first*x+a.second;
}

void insert(P x,int node=0,long long nodel=-INF,long long noder=INF){
    P low=seg[node].line;
    P high=x;
    long long mid=(nodel+noder)/2;
    if (f(low,nodel)>f(high,nodel)) {
        swap(low,high);
    }
    if (f(high,noder)>=f(low,noder)) {
        seg[node].line=high;
        return;
    }
    if (f(low,mid)>=f(high,mid)) {
        seg[node].line=low;
        if (seg[node].l==-1) {
            seg[node].l=seg.size();
            seg.push_back(emp);
        }
        insert(high,seg[node].l,nodel,mid);
    }
    else {
        seg[node].line=high;
        if (seg[node].r==-1) {
            seg[node].r=seg.size();
            seg.push_back(emp);
        }
        insert(low,seg[node].r,mid+1,noder);
    }
}

long long gety(long long x){
    int node=0;
    int nodel=-INF;
    int noder=INF;
    long long ret=-8e18;
    while (node!=-1) {
        ret=max(ret,f(seg[node].line,x));
        long long mid=(nodel+noder)/2;
        if (x<=mid){
            node=seg[node].l;
            noder=mid;
        }
        else {
            node=seg[node].r;
            nodel=mid+1;
        }
    }
    return ret;
}

P query[3000000];
long long ret[3000000];
typedef pair<P,int> Pi;
vector<Pi> vec;

bool comp(Pi a,Pi b) {
    if (a.first.second==b.first.second) {
        if (a.first.first==b.first.first){
            return a.second>b.second;
        }
        return a.first.first>b.first.first;
    }
    return a.first.second>b.first.second;
}


int main() {
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++) {
        long long t,a,b,c;
        scanf("%lld %lld %lld %lld",&t,&a,&b,&c);
        long long x1=t+a;
        long long y1=t-a;
        long long x2=t+abs(b-a)+b;
        long long y2=t+abs(b-a)-b;
        c/=2;
        v.push_back(PPi(PP(P(x1,y1),P(x2,y2)),c));
        px.push_back(x1);
        px.push_back(x2);
        py.push_back(y1);
        py.push_back(y2);
    }
    sort(px.begin(),px.end());
    px.erase(unique(px.begin(),px.end()),px.end());
    sort(py.begin(),py.end());
    py.erase(unique(py.begin(),py.end()),py.end());
    for(int i=0;i<n;i++) {
        v[i].first.first.first=lower_bound(px.begin(),px.end(),v[i].first.first.first)-px.begin();
        v[i].first.first.second=lower_bound(py.begin(),py.end(),v[i].first.first.second)-py.begin();
        v[i].first.second.first=lower_bound(px.begin(),px.end(),v[i].first.second.first)-px.begin();
        v[i].first.second.second=lower_bound(py.begin(),py.end(),v[i].first.second.second)-py.begin();
        if (v[i].first.first.second==v[i].first.second.second) {
            for(int j=v[i].first.first.first;j<v[i].first.second.first;j++) {
                arr[j][v[i].first.first.second][0]=max(arr[j][v[i].first.first.second][0],v[i].second);
            }
        }
        else {
            for(int j=v[i].first.first.second;j<v[i].first.second.second;j++) {
                arr[v[i].first.first.first][j][1]=max(arr[v[i].first.first.first][j][1],v[i].second);
            }
        }
    }
    for(int i=px.size()-1;i>=0;i--) {
        for(int j=py.size()-1;j>=0;j--) {
            if (i+1<px.size()) {
                dp[i][j]=max(dp[i][j],dp[i+1][j]+1LL*arr[i][j][0]*(px[i+1]-px[i]));
            }
            if (j+1<py.size()) {
                dp[i][j]=max(dp[i][j],dp[i][j+1]+1LL*arr[i][j][1]*(py[j+1]-py[j]));
            }
        }
    }
    for(int i=0;i<q;i++) {
        int t,pos;
        scanf("%d %d",&t,&pos);
        int x=t+pos;
        int y=t-pos;
        query[i]=P(x,y);
        int xind=lower_bound(px.begin(),px.end(),x)-px.begin();
        int yind=lower_bound(py.begin(),py.end(),y)-py.begin();
        if (xind==px.size()||yind==py.size()) {
            ret[i]=0;
            continue;
        }
        vec.push_back(Pi(P(xind,yind),i));
        ret[i]=dp[xind][yind];
    }
    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());
    int ind=0;
    for(int i=px.size()-1;i>0;i--) {
        seg.clear();
        seg.push_back(emp);
        int pr=py.size();
        while (ind<vec.size()&&vec[ind].first.first==i) {
            for(int j=pr-1;j>=vec[ind].first.second;j--) {
                insert(P(-arr[i-1][j][0],1LL*arr[i-1][j][0]*px[i]+dp[i][j]));
                //printf(".%d %lld\n",-arr[i-1][j][0],1LL*arr[i-1][j][0]*px[i]+dp[i][j]);
            }
            pr=vec[ind].first.second;
            int now=vec[ind].second;
//printf("%d %lld\n",now,gety(query[now].first));
            ret[now]=max(ret[now],gety(query[now].first));
            ind++;
        }
    }
    sort(vec.begin(),vec.end(),comp);
    ind=0;
    for(int i=py.size()-1;i>0;i--) {
        seg.clear();
        seg.push_back(emp);
        int pr=px.size();
        while (ind<vec.size()&&vec[ind].first.second==i) {
            for(int j=pr-1;j>=vec[ind].first.first;j--) {
                insert(P(-arr[j][i-1][1],1LL*arr[j][i-1][1]*py[i]+dp[j][i]));
                //printf("%lld %lld\n",-arr[j][i-1][1],1LL*arr[j][i-1][1]*py[i]+dp[j][i]);
            }
            pr=vec[ind].first.first;
            int now=vec[ind].second;
            ret[now]=max(ret[now],gety(query[now].second));
            ind++;
        }
    }
    for(int i=0;i<q;i++) {
        printf("%lld\n",ret[i]);
    }
    return 0;
}

Compilation message

bodyguard.cpp: In function 'long long int gety(long long int)':
bodyguard.cpp:58:15: warning: overflow in conversion from 'long long int' to 'int' changes value from '-3000000007' to '1294967289' [-Woverflow]
   58 |     int nodel=-INF;
      |               ^~~~
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             if (i+1<px.size()) {
      |                 ~~~^~~~~~~~~~
bodyguard.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |             if (j+1<py.size()) {
      |                 ~~~^~~~~~~~~~
bodyguard.cpp:146:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         if (xind==px.size()||yind==py.size()) {
      |             ~~~~^~~~~~~~~~~
bodyguard.cpp:146:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         if (xind==px.size()||yind==py.size()) {
      |                              ~~~~^~~~~~~~~~~
bodyguard.cpp:160:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         while (ind<vec.size()&&vec[ind].first.first==i) {
      |                ~~~^~~~~~~~~~~
bodyguard.cpp:178:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |         while (ind<vec.size()&&vec[ind].first.second==i) {
      |                ~~~^~~~~~~~~~~
bodyguard.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
bodyguard.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         scanf("%lld %lld %lld %lld",&t,&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         scanf("%d %d",&t,&pos);
      |         ~~~~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 3854 ms 322772 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 278884 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 278884 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 278884 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3854 ms 322772 KB Output isn't correct
2 Halted 0 ms 0 KB -