[TIOJ 1396] 線段覆蓋

原題：http://tioj.ck.tp.edu.tw/problems/1396
AC：http://tioj.ck.tp.edu.tw/submissions/17674

解題方向：單調性，貪心法


題目大意：兩個人分別有不同的兩組線段，有標記放置的位置，試問誰能用最少的線段覆蓋指定區間。

解法：我們可以分開計算兩個人所需的線段，把線段排序後，由左向右掃描，檢查最右界是否能到達終點即可。

本方法最費時間的為排序，總複雜度為$O(n\log n)$

透過特判可以把時間壓到$140ms$，不過$visitorIKC$的$61ms$我還沒頭緒，是不是能在優化到線性複雜度呢? (對方表示他只是極致的壓常數

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    pair<int,int> d[2][100000];
    int N[2];
    int X,Y;
    int ans[2];
    register int i,j,mx,ed;
    bool flag;
    while( cin>>N[0]>>N[1] )
    {
        ans[0]=ans[1]=INT_MAX;
        for(i=0;i<2;++i)
            for(j=0;j<N[i];++j)
                cin>>d[i][j].first>>d[i][j].second;
        cin>>X>>Y;
        flag = false;
        if( X == Y ) {
            for(i=0;i<100000000;++i);
            for(i=0;i<2;++i)
                for(j=0;j<N[i];++j)
                    if( d[i][j].first <= X && X <= d[i][j].second )
                    {
                        ans[i] = 1 ;
                        break;
                    }
        }
        else
        {
            sort(d[0],d[0]+N[0]);
            sort(d[1],d[1]+N[1]);
            for(i=0;i<2;++i)
            {
                ed = mx = X;
                j = 0;
                while( j!=N[i] && ed < Y )
                {
                    ans[i]++;
                    ed = mx;
                    flag = false;
                    while( j!=N[i] && d[i][j].first <= ed ) {
                        if( d[i][j].second > mx )
                        {
                            flag = true;
                            mx = d[i][j].second;
                        }
                        j++;
                    }
                    if( !flag ) break;
                }
                if( mx < Y ) ans[i] = INT_MAX;
            }
        }
        if( ans[0] == ans[1] && ans[0] == INT_MAX ) cout<<"TIE\n";
        else if( ans[0] <= ans[1] ) cout<<"A WIN\n";
        else cout<<"B WIN\n";
    }
}