(IOI) 2009 Day 2 p4 Salesman

https://contest.yandex.com/ioi/contest/1363/problems/H/

這題有個關鍵(?) ： 所有的位置 (展覽 + 家) 都不一樣。

所以，先考慮 60 pts (沒有兩個展覽在同一天)，這個可以用DP去實現。

dp[i] --> 在位置 i 當作最後一個 展覽，最佳的獲利是多少。

這樣一來， dp[i] = max( dp[j] + cost(i,j) ) ， 其中 cost (i,j) 是 位置 i  到位置 j 的距離。

因為距離的cost有兩種：一種是 用 U 的，一種是用 D 的，所以要開兩個線段樹分別存下來(?

這樣，就可以在 O(N lg N) 的複雜度解決這題。

接下來，考慮 有多個展覽在同一天。

可以發現，對於最佳解，有一個固定的pattern是：先走到某一個展覽，在一直延那個展覽往右 / 往左走。

於是，好好地用上面那個線段樹搞一搞，就okay惹~

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
#define F first
#define S second

#define SZ(x) ((int)(x).size())

pii operator+(const pii &p1,const pii &p2)
{
    return make_pair(max(p1.F,p2.F),max(p1.S,p2.S));
}

const int INF = 2000000009;
const int POS_MAX = 500004;
const int POS_MIN = -1;

pii ee = make_pair(-INF,-INF);

struct Node
{
    Node *lc,*rc;
    pii val;
    Node():lc(NULL),rc(NULL),val(ee){}
    void pull()
    {
        val = (lc->val + rc->val);
    }
};

Node* Build(int L,int R)
{
    Node* node = new Node();
    if (L==R)
    {
        return node;
    }
    int mid=(L+R)>>1;
    node->lc = Build(L,mid);
    node->rc = Build(mid+1,R);
    return node;
}

void modify(Node* node,int L,int R,int pos,pii val)
{
    if (L == R)
    {
        node->val = val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos <= mid) modify(node->lc,L,mid,pos,val);
    else modify(node->rc,mid+1,R,pos,val);
    node->pull();
}

pii query(Node* node,int L,int R,int l,int r)
{
    if (l>R || L>r) return ee;
    else if (l<=L && R<=r) return node->val;
    int mid=(L+R)>>1;
    return (query(node->lc,L,mid,l,r) + query(node->rc,mid+1,R,l,r));
}

int dp[POS_MAX];

int t[POS_MAX],l[POS_MAX],m[POS_MAX];

vector<int> tt[POS_MAX];

int main ()
{
    int n,u,d,s;
    scanf("%d %d %d %d",&n,&u,&d,&s);
    ++s;
    int nn = 500003;
    Node* root = Build(1,nn);
    for (int i=1;n>=i;i++)
    {
        scanf("%d %d %d",&t[i],&l[i],&m[i]);
        ++l[i];
        tt[ t[i] ].push_back(i);
    }
    //swap(d,u);
    modify(root,1,nn,s, make_pair( dp[s]-(s-POS_MIN)*u , dp[s]-(POS_MAX-s)*d ) );
    for (int ii=1;nn>=ii;ii++)
    {
        //if (SZ(tt[ii]) != 1) continue;
        //cout << "ii = " << ii << endl;
        if (SZ(tt[ii]) >= 1)
        {
            for (int i:tt[ii])
            {
                pii p = query(root,1,nn,1,l[i]-1);
                pii q = query(root,1,nn,l[i]+1,nn);
                int mx = -INF;
                if (p.S != -INF)
                {
                    mx = max(mx,p.S + (POS_MAX-l[i])*d);
                }
                if (q.F != -INF)
                {
                    mx = max(mx,q.F + (l[i]-POS_MIN)*u);
                }
                dp[ l[i] ] = mx + m[i];
                //cout << "dp [ " << l[i] << " ] = " << dp[ l[i] ] << endl;
                //modify(root,1,nn,l[i], make_pair( dp[ l[i] ]-( l[i] -POS_MIN)*u , dp[ l[i] ]-(POS_MAX- l[i] )*d ) );
            }
            for (int i:tt[ii])
            {
                modify(root,1,nn,l[i], make_pair( dp[ l[i] ]-( l[i] -POS_MIN)*u , dp[ l[i] ]-(POS_MAX- l[i] )*d ) );
            }
        }
        if (SZ(tt[ii]) > 1)
        {
            sort(tt[ii].begin(),tt[ii].end(),[](const int &a,const int &b)
             {
                 return l[a] < l[b];
             });
            //starting from l --> r
            pii ptmp = query(root,1,nn,1,l[ tt[ii][0] ]-1);
            int lmax = ptmp.S;
            for (int iii=0;SZ(tt[ii])>iii;iii++)
            {
                int i = tt[ii][iii];
                dp[ l[i] ] = max( dp[ l[i] ], lmax + (POS_MAX - l[i])*d + m[i] );
                lmax += m[i];
                if (iii == SZ(tt[ii]) - 1) break;
                int nxti = tt[ii][iii+1];
                pii qtmp = query(root,1,nn,l[i],l[nxti]-1);
                lmax = max(lmax,qtmp.S);
            }
            //starting from r --> l
            reverse(tt[ii].begin(),tt[ii].end());
            ptmp = query(root,1,nn,l[ tt[ii][0] ]+1,nn);
            int rmax = ptmp.F;
            for (int iii=0;SZ(tt[ii])>iii;iii++)
            {
                int i = tt[ii][iii];
                dp[ l[i] ] = max( dp[ l[i] ], rmax + (l[i] - POS_MIN)*u + m[i]);
                rmax += m[i];
                if (iii == SZ(tt[ii]) - 1) break;
                int nxti = tt[ii][iii+1];
                pii qtmp = query(root,1,nn,l[nxti]+1,l[i]);
                rmax = max(rmax,qtmp.F);
            }
            /*reverse(tt[ii].begin(),tt[ii].end());
            for (int iii=1;SZ(tt[ii])>iii;iii++)
            {
                int i = tt[ii][iii];
                int prei = tt[ii][iii-1];
                dp[i] = max(dp[i],dp[prei] + (l[i] - l[prei])*d);
            }
            reverse(tt[ii].begin(),tt[ii].end());
            for (int iii=1;SZ(tt[ii])>iii;iii++)
            {
                int i = tt[ii][iii];
                int prei = tt[ii][iii-1];
                dp[i] = max(dp[i],dp[prei] + (l[prei] - l[i])*u);
            }*/
            for (int i:tt[ii])
            {
                modify(root,1,nn,l[i], make_pair( dp[ l[i] ]-( l[i] -POS_MIN)*u , dp[ l[i] ]-(POS_MAX- l[i] )*d ) );
            }
        }
    }
    //swap(d,u);
    int ans = 0;
    for (int i=1;POS_MAX>i;i++)
    {
        /*if (dp[i])
        {
            cout << "i = " << i << " , dp = " <<dp[i] << endl;
        }*/
        if (i < s)
        {
            ans = max(ans,dp[i] - (s-i)*d);
        }
        else
        {
            ans = max(ans,dp[i] - (i-s)*u);
        }
    }
    printf("%d\n",ans);
}