Submission #1145116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145116		t9unkubj	Bodyguard (JOI21_bodyguard)	C++20	0 / 100	7497 ms	2162688 KiB

bodyguard

#ifdef t9unkubj

#define _GLIBCXX_DEBUG
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
struct man{
    ll sx,sy;
    ll tx,ty;
    ll lsx,lsy;
    ll ltx,lty;
    ll c;
    int type(){
        return sx==tx;
    }
};
struct cht{
    using P=array<ll,3>;
    deque<P>dq;
    ll last_b;
    cht():last_b(-2e18){
        dq.push_back(P{(ll)2e9,(ll)-2e18,(ll)2e18});
    }
    ll eval(P a,ll x){
        return a[0]*x+a[1];
    }
    ll compare(P a,P b){

        return (b[1]-a[1]+a[0]-b[0]-1)/(a[0]-b[0]);
    }
    void add(ll a,ll b){
        assert(last_b<=b);
        chmax(last_b,b);
        while(dq.size()>=2&&(dq.back()[0]<=a||dq.back()[2]<=compare(dq.back(),P{a,b,0}))){
            dq.pop_back();
        }
        dq.push_back({a,b,compare(dq.back(),P{a,b,0})});    
    }
    ll get_max(ll x){
        int ac=0,wa=dq.size();
        while(wa-ac>1){
            int wj=ac+wa>>1;
            if(dq[wj][2]>=x)ac=wj;
            else wa=wj;
        }
        return eval(dq[ac],x);
    }
};
void solve(){
    int n,q;
    cin>>n>>q;
    vc<ll>t(n),a(n),b(n),c(n);
    rep(i,n)cin>>t[i]>>a[i]>>b[i]>>c[i];
    vc<man>mn;

    map<ll,ll>cx;
    rep(i,n){
        ll x1=a[i];
        ll y1=t[i];
        ll x2=b[i];
        ll y2=t[i]+abs(b[i]-a[i]);
        ll X1=x1+y1;
        ll Y1=y1-x1;
        ll X2=x2+y2;
        ll Y2=y2-x2;
        cx[X1]=cx[X2]=0;
        cx[Y1]=cx[Y2]=0;
        mn.push_back({X1,Y1,X2,Y2,0,0,0,0,c[i]/2});
    }
    cx[-2e9]=cx[-2e9]=0;
    cx[2e9+10]=cx[2e9+10]=0;
    int id=0;for(auto&[x,y]:cx)y=id++;

    vc<ll>X;
    for(auto&[x,y]:cx)X.push_back(x);
    rep(i,n){
        auto&[sx,sy,tx,ty,lsx,lsy,ltx,lty,c]=mn[i];
        lsx=cx[sx];
        lsy=cx[sy];
        ltx=cx[tx];
        lty=cx[ty];   
    }
    int m=cx.size();
    vvc<ll>dp(m,vc<ll>(m));
    vvc<ll>tx(m,vc<ll>(m));
    auto ty=tx;
    rep(i,n){
        //縦長
        if(mn[i].type()){
            REP(j,mn[i].lsy,mn[i].lty){
                chmax(ty[mn[i].lsx][j],mn[i].c);
            }
        }else{
            REP(j,mn[i].lsx,mn[i].ltx){
                chmax(tx[j][mn[i].lsy],mn[i].c);
            }
        }
    }
    
    vc<ll>ans(q);
    vc<array<ll,4>>event;
    rep(i,m)rep(j,m){
        event.push_back({X[i]+X[j],(ll)1e9,i,j});
    }

    rep(i,q){
        int x,p;
        cin>>p>>x;
        ll X1=x+p;
        ll Y1=-x+p;
        auto ix=lower_bound(all(X),X1)-X.begin();
        auto iy=lower_bound(all(X),Y1)-X.begin();
        
        event.push_back({X[ix]+X[iy],i,X1,Y1});
    }
    sort(rall(event));
    vc<cht>CHTX(m),CHTY(m);
    vc<ll>mx(m),my(m);
    for(auto&[v,i,x,y]:event){
        if(i==1e9){
            if(x+1<m)chmax(dp[x][y],dp[x+1][y]+tx[x][y]*(X[x+1]-X[x])),chmax(mx[x],mx[x+1]);
            if(y+1<m)chmax(dp[x][y],dp[x][y+1]+ty[x][y]*(X[y+1]-X[y])),chmax(my[y],my[y+1]);
            //if(x)CHTX[x].add(tx[x-1][y],dp[x][y]);
            //if(y)CHTY[y].add(ty[x][y-1],dp[x][y]);
            chmax(mx[x],dp[x][y]);
            chmax(my[y],dp[x][y]);
        }else{
            auto ix=lower_bound(all(X),x)-X.begin();
            auto iy=lower_bound(all(X),y)-X.begin();
            //ans[i]=max(CHTX[ix].get_max(X[ix]-x),CHTY[iy].get_max(X[iy]-y));
            chmax(ans[i],mx[ix]);
            chmax(ans[i],my[iy]);
        }
    }
    rep(i,q)cout<<ans[i]<<"\n";
}

signed main(){
#ifdef t9unkubj
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
    cin.tie(0)->sync_with_stdio(0);
    pass_time=clock();
    int t=1;
    //cin>>t;
    while(t--)solve();
    pass_time=clock()-pass_time;
    dbg(pass_time/CLOCKS_PER_SEC);
}
/*
3 2
 3 1 5 2
 1 4 1 4
 4 2 4 4
 2 2
 6 3
*/

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 52