Submission #903989

#	Time	Username	Problem	Language	Result	Execution time	Memory
903989		ansol4328	Salesman (IOI09_salesman)	C++14	32 / 100	1244 ms	65536 KiB

salesman

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=1e18;

struct SegTree{
    vector<ll> mx, lz;
    int base;
    SegTree(int a){
        base=1;
        while(base<a) base<<=1;
        mx.resize(base*2);
        lz.resize(base*2);
    }
    void pro(int ns, int nf, int num){
        if(ns<nf && lz[num]){
            lz[num*2]+=lz[num];
            lz[num*2+1]+=lz[num];
        }
        mx[num]+=lz[num];
        lz[num]=0;
    }
    void add(ll v, int st, int fn, int ns=1, int nf=-1, int num=1){
        if(nf==-1) nf=base;
        pro(ns,nf,num);
        if(nf<st || fn<ns) return;
        if(st<=ns && nf<=fn){
            lz[num]+=v;
            pro(ns,nf,num);
            return;
        }
        int mid=(ns+nf)>>1;
        add(v,st,fn,ns,mid,num*2);
        add(v,st,fn,mid+1,nf,num*2+1);
        mx[num]=max(mx[num*2],mx[num*2+1]);
    }
    ll qry(int st, int fn, int ns=1, int nf=-1, int num=1){
        if(nf==-1) nf=base;
        pro(ns,nf,num);
        if(nf<st || fn<ns) return -INF;
        if(st<=ns && nf<=fn) return mx[num];
        int mid=(ns+nf)>>1;
        return max(qry(st,fn,ns,mid,num*2),qry(st,fn,mid+1,nf,num*2+1));
    }
};

struct fenwick{
    vector<ll> s;
    int sz;
    fenwick(int a) : s(a+5), sz(a) {}
    void updt(int i, int v){
        for(; i<=sz ; i+=i&-i) s[i]+=v;
    }
    ll qry(int i){
        ll ret=0;
        for(; i ; i-=i&-i) ret+=s[i];
        return ret;
    }
};

ll N, U, D, S;
vector<P> lst[500005];
ll dp[500005];
const int E=500001;

int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin >> N >> U >> D >> S;
    for(int i=1 ; i<=N ; i++){
        int x, y, z;
        cin >> x >> y >> z;
        lst[x].pb({y,z});
    }
    SegTree L(E), R(E);
    fenwick SL(E), SR(E);
    for(int i=1 ; i<=E ; i++){
        if(i<=S) dp[i]=-U*(S-i);
        else dp[i]=-D*(i-S);
        L.add(dp[i]+D*i,i,i);
        R.add(dp[i]-U*i,i,i);
    }
    for(int i=1 ; i<E ; i++){
        for(auto& [y, z] : lst[i-1]){
            SL.updt(y,-z), SR.updt(E-y+1,-z);
            if(y<E) L.add(z,y+1,E);
            if(y>1) R.add(z,1,y-1);
        }
        for(auto& [y, z] : lst[i]){
            SL.updt(y,z), SR.updt(E-y+1,z);
            if(y<E) L.add(-z,y+1,E);
            if(y>1) R.add(-z,1,y-1);
        }
        vector<vector<ll>> tmp;
        for(auto& [y, z] : lst[i]){
            ll pr=dp[y];
            if(y>1){
                dp[y]=max(dp[y], -D*y+SL.qry(y)+L.qry(1,y-1));
                // cout << L.qry(1,y-1) << ' ';
                // cout << -D*y+SL.qry(y)+L.qry(1,y-1) << "  |  ";
            }
            if(y<E){
                dp[y]=max(dp[y], U*y+SR.qry(E-y+1)+R.qry(y+1,E));
                // cout << R.qry(y+1,E) << ' ';
                // cout << U*y+SR.qry(E-y+1)+R.qry(y+1,E) << ' ';
            }
            if(pr!=dp[y]) tmp.pb({y,pr,dp[y]});
            // cout << dp[y];
            // cout << endl;
        }
        for(auto &v : tmp){
            L.add(-v[1]+v[2],v[0],v[0]);
            R.add(-v[1]+v[2],v[0],v[0]);
        }
    }
    ll ans=0;
    for(int i=1 ; i<=E ; i++){
        if(i<=S) ans=max(ans,dp[i]-D*(S-i));
        else ans=max(ans,dp[i]-U*(i-S));
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:88:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |         for(auto& [y, z] : lst[i-1]){
      |                   ^
salesman.cpp:93:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |         for(auto& [y, z] : lst[i]){
      |                   ^
salesman.cpp:99:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |         for(auto& [y, z] : lst[i]){
      |                   ^

• Subtask 1: 32 / 100