2013 2 A - Ticket Swapping

domen111

題目(懶得翻譯了): https://code.google.com/codejam/contest/2442487/dashboard#s=p0

這題基本上，是哪一個人的進出已經不重要，你可以把每個進出分開思考。
用括號表示，括號代表進出的順序，範例測資可轉換成:
1. ()()
2. ()()
3. (())
之所以解成括號，就表示這題是其實是個類似括號匹配問題，用stack可解決。
我自己花了一段時間有想出這題是括號匹配問題，不過沒有嚴謹的證明，大概可以簡單說明:

用三角形代表每段價錢，看得懂就看吧

AC CODE:
(寫出一個蠢bug，34行m*2寫成n)

#include<bits/stdc++.h>

#define MOD 1000002013

using namespace std;

struct item{

    long long count;

    long long pos;

    char lr;

    bool operator<(item b)const

    {

        if(this->pos!=b.pos)

            return this->pos<b.pos;

        else

            return this->lr<b.lr;

    }

    item(long long count,long long pos,char lr)

    {

        this->count=count;

        this->pos=pos;

        this->lr=lr;

    }

    item(){}

};

int n,m;

item data[2010];

long long cal(long long o,long long e,long long p)

{

    long long l=e-o;

    return (((n+n-l+1)*l/2)%MOD) * p %MOD;

}

long long solve()

{

    stack<item> stk;

    long long ans=0;

    for(int i=0;i<m*2;i++)

    {

        if(data[i].lr=='(')

        {

            stk.push(data[i]);

        }

        else

        {

            long long left=data[i].count;

            while(left!=0)

            {

                long long change=min(left,stk.top().count);

                ans+=cal(stk.top().pos,data[i].pos,change);

                ans%=MOD;

                stk.top().count-=change;

                left-=change;

                if(stk.top().count==0)

                    stk.pop();

            }

        }

    }

    return ans;

}

int main()

{

    int T;

    cin>>T;

    for(int no=1;no<=T;no++)

    {

        memset(data,0,sizeof data);

        cin>>n>>m;

        long long origin=0,swapped=0;

        for(int i=0;i<m;i++)

        {

            long long o,e,p;

            cin>>o>>e>>p;

            origin+=cal(o,e,p);

            origin%=MOD;

            

            data[i*2]=item(p,o,'(');

            data[i*2+1]=item(p,e,')');

        }

        sort(data,data+m*2);

        swapped=solve();

        printf("Case #%d: %lld\n",no,(origin-swapped+MOD)%MOD);

    }

}