Submission #524711

#	Time	Username	Problem	Language	Result	Execution time	Memory
524711		Deepesson	Salesman (IOI09_salesman)	C++17	100 / 100	1595 ms	65536 KiB

salesman

#include <bits/stdc++.h>
#define MAX 505000
using ll = int;
ll inf = (1e9);
struct Seg3 {

    ll tab[MAX*4];

    void update(int t,ll k,int la=0,int ra=MAX-1,int pos=1){
        if(la>t||ra<t)return;
        if(la==ra){
            tab[pos]=std::max(tab[pos],k);
            return;
        }
        int m = (la+ra)/2;
        update(t,k,la,m,pos*2);
        update(t,k,m+1,ra,(pos*2)+1);
        tab[pos]=std::max(tab[pos*2],tab[(pos*2)+1]);
    }

    ll query(int l,int r,int la=0,int ra=MAX-1,int pos=1){
        if(la>r||ra<l)return -inf;
        if(la>=l&&ra<=r){
            return tab[pos];
        }
        int m = (la+ra)/2;
        return std::max(query(l,r,la,m,pos*2),query(l,r,m+1,ra,(pos*2)+1));
    }

    void iniciar(void){
        for(auto&x:tab)x=-inf;
    }

};

ll U,D;
ll Q,S;
Seg3 upper,down,upper2,down2;
typedef std::pair<ll,ll> pll;
typedef std::pair<ll,pll> plp;
int main()
{

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    upper.iniciar();
    upper2.iniciar();
    down.iniciar();
    down2.iniciar();

    std::cin>>Q>>D>>U>>S;

    upper.update(S,+(U*S));
    down.update(S,-(D*S));
    upper2.update(S,+(U*S));
    down2.update(S,-(D*S));

    std::vector<plp> eventos;
    eventos.push_back(plp(inf,pll(S,0)));

    for(int i=0;i!=Q;++i){
        ll D,L,X;
        std::cin>>D>>L>>X;
        eventos.push_back({D,{L,X}});
    }

    std::sort(eventos.begin(),eventos.end());
    std::vector<pll> upd,upu;
    std::vector<std::vector<plp>> evndias;
    std::vector<plp> u;
    ll last=-1;
    for(auto&x:eventos){
        if(x.first!=last){
            evndias.push_back(u);
            u.clear();
            last=x.first;
        }
        u.push_back(x);
    }
    evndias.push_back(u);
    last=0;
    for(auto&y:evndias){
        std::vector<pll> upu,upd;
        for(auto&x:y){
            ll local = x.second.first;
            ll bonus = x.second.second;
            ll descer = down.query(local,MAX-1);
            ll subir = upper.query(0,local-1);
            ll ans = std::max(descer+bonus+(D*local),subir+bonus-(U*local));
            last=ans;
            down.update(local,ans-(D*local));
            upper.update(local,ans+(U*local));
            upd.push_back({local,ans-(D*local)});
            upu.push_back({local,ans+(U*local)});
        }
        std::reverse(y.begin(),y.end());
        for(auto&x:y){
            ll local = x.second.first;
            ll bonus = x.second.second;
            ll descer = down2.query(local,MAX-1);
            ll subir = upper2.query(0,local-1);
            ll ans = std::max(descer+bonus+(D*local),subir+bonus-(U*local));
            last=ans;
            down2.update(local,ans-(D*local));
            upper2.update(local,ans+(U*local));
            upd.push_back({local,ans-(D*local)});
            upu.push_back({local,ans+(U*local)});
        }
        for(auto&x:upd){
            down.update(x.first,x.second);
            down2.update(x.first,x.second);
        }
        for(auto&x:upu){
            upper.update(x.first,x.second);
            upper2.update(x.first,x.second);
        }
    }
    std::cout<<last<<"\n";
}

• Subtask 1: 100 / 100