Submission #593318

#	Time	Username	Problem	Language	Result	Execution time	Memory
593318		Bench0310	Salesman (IOI09_salesman)	C++17	100 / 100	640 ms	23884 KiB

salesman

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=500001;
int mvl,mvr;
int tlee[4*N]; //left endpoint
int tree[4*N]; //right endpoint
array<int,3> fairs[N];
int best[N];

void update(int idx,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tlee[idx]=val-mvr*l;
        tree[idx]=val+mvl*l;
    }
    else
    {
        int m=(l+r)/2;
        if(pos<=m) update(2*idx,l,m,pos,val);
        else update(2*idx+1,m+1,r,pos,val);
        tlee[idx]=max(tlee[2*idx],tlee[2*idx+1]);
        tree[idx]=max(tree[2*idx],tree[2*idx+1]);
    }
}

int query(int idx,int l,int r,int ql,int qr,int t)
{
    if(ql>qr) return -(1<<30);
    if(l==ql&&r==qr) return (t==0?tlee[idx]:tree[idx]);
    int m=(l+r)/2;
    return max(query(2*idx,l,m,ql,min(qr,m),t),query(2*idx+1,m+1,r,max(ql,m+1),qr,t));
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(tlee,128,sizeof(tlee));
    memset(tree,128,sizeof(tree));
    memset(best,128,sizeof(best));
    int n,s;
    cin >> n >> mvl >> mvr >> s;
    mvl=-mvl; mvr=-mvr;
    for(int i=0;i<n;i++) for(int j=0;j<3;j++) cin >> fairs[i][j];
    sort(fairs,fairs+n);
    update(1,1,N,s,0);
    auto getopt=[&](int p)->int
    {
        return max(query(1,1,N,1,p,0)+mvr*p,query(1,1,N,p,N,1)-mvl*p);
    };
    auto chmax=[&](int &a,int b){a=max(a,b);};
    int tl=0;
    while(tl<n)
    {
        int tr=tl;
        while(tr+1<n&&fairs[tr+1][0]==fairs[tl][0]) tr++;
        int opt=-(1<<30);
        for(int i=tl;i<=tr;i++)
        {
            auto [t,p,c]=fairs[i];
            int now=max(getopt(p),opt+mvr*p)+c;
            chmax(best[i],now);
            chmax(opt,now-mvr*p);
        }
        opt=-(1<<30);
        for(int i=tr;i>=tl;i--)
        {
            auto [t,p,c]=fairs[i];
            int now=max(getopt(p),opt-mvl*p)+c;
            chmax(best[i],now);
            chmax(opt,now+mvl*p);
        }
        for(int i=tl;i<=tr;i++) update(1,1,N,fairs[i][1],best[i]);
        tl=tr+1;
    }
    cout << getopt(s) << "\n";
    return 0;
}

• Subtask 1: 100 / 100