Submission #754277

#	Time	Username	Problem	Language	Result	Execution time	Memory
754277		bgnbvnbv	Salesman (IOI09_salesman)	C++14	62 / 100	795 ms	56328 KiB

salesman

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=5e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
struct node
{
    ll be ,lon;
    node ()
    {
        be=-inf;
        lon=-inf;
    }
    node operator+(const node&o)
    {
        node ans;
        ans.be=max(be,o.be);
        ans.lon=max(lon,o.lon);
        return ans;
    }
}st[4*maxN];
ll o,u,d;
void update(ll pos,ll val,ll id=1,ll l=1,ll r=o)
{
    if(l==r)
    {
        st[id].lon=val-pos*u;
        st[id].be=val+pos*d;
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(pos,val,id*2,l,mid);
    else update(pos,val,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
node get(ll i,ll j,ll id=1,ll l=1,ll r=o)
{
    if(j<l||r<i) return node();
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r);
}
ll n,s;
struct qq
{
    ll t,l,m;
    bool operator<(const qq&o)
    {
        return t<o.t;
    }
}e[maxN];
pli a[maxN];
ll val[maxN];
void solve()
{
    cin >> n >> u >> d >> s;
    o=s;
    for(int i=1;i<=n;i++)
    {
        cin >> e[i].t >> e[i].l >> e[i].m;
        o=max(o,e[i].l);
    }
    sort(e+1,e+n+1);
    ll ans=0;
    update(s,0);
    for(int i=1;i<=n;i++)
    {
        ll j=i;
        while(j<=n&&e[j].t==e[i].t)
        {
            a[j-i+1]={e[j].l,e[j].m};
            j++;
        }
        sort(a+1,a+j-i+1);
        for(int k=1;k<=j-i;k++)
        {
            val[a[k].fi]=max(get(a[k].fi+1,o).lon+a[k].fi*u+a[k].se,get(1,a[k].fi-1).be-a[k].fi*d+a[k].se);
        }
        sort(a+1,a+j-i+1,greater<pli>());
        for(int k=1;k<=j-i;k++)
        {
            val[a[k].fi]=max({val[a[k].fi],get(a[k].fi+1,o).lon+a[k].fi*u+a[k].se,get(1,a[k].fi-1).be-a[k].fi*d+a[k].se});
            val[a[k].fi]=max(val[a[k].fi],-inf);
            update(a[k].fi,val[a[k].fi]);
            if(a[k].fi<s) ans=max(ans,val[a[k].fi]-abs(s-a[k].fi)*d);
            else ans=max(ans,val[a[k].fi]-abs(s-a[k].fi)*u);
        }
        //cout <<val[a[1].fi]<<' ';
        i=j-1;
    }
    cout << ans;
    //6h30 xuong dao
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

salesman.cpp: In function 'void update(ll, ll, ll, ll, ll)':
salesman.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     ll mid=l+r>>1;
      |            ~^~
salesman.cpp: In function 'node get(ll, ll, ll, ll, ll)':
salesman.cpp:47:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     ll mid=l+r>>1;
      |            ~^~

• Subtask 1: 62 / 100