[TIOJ 1216] 好想睡覺 之 好累的大頭蕃

作法：

因為這題數字範圍小小的，所以沒想比較好的作法。首先看每個房間，如果裡面的線段有重疊到的話就先合併起來，然後對每個房間的每個時間點記錄從那個點開始還能睡多久，每個詢問都O(n) 回答，就能過這題了。但 TIOJ 1223 是這題的強化版，作法在這裡。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100+10,maxt=10000+10 ;
struct P
{
    int x,y ;
    bool operator < (const P &rhs) const
    {
        return x==rhs.x ? y<rhs.y : x<rhs.x ;
    }
};
 
P tmp[maxt] ;
void cal(vector<P> &v)
{
    sort(v.begin(),v.end()) ;
    int cnt=0 ;
    for(auto i : v)
    {
        if(!cnt) { tmp[cnt++]=i ; continue ; }
        if(tmp[cnt-1].y >= i.y) continue ;
        else if(i.x <= tmp[cnt-1].y)
            tmp[cnt-1].y=max(tmp[cnt-1].y,i.y) ;
        else tmp[cnt++]=i ;
    }
    for(int i=0;i<cnt;i++) v[i]=tmp[i] ;
    v.resize(cnt) ;
}
 
vector<P> v[maxn] ;
int dis[maxn][maxt] ;
 
main()
{
    int n,t ;
    while(scanf("%d%d",&n,&t)==2 && n+t)
    {
        for(int i=1;i<=n;i++) v[i].clear() ;
        int m ; scanf("%d",&m) ;
        while(m--)
        {
            int id,x,y ; scanf("%d%d%d",&id,&x,&y) ;
            v[id].push_back((P){x,y}) ;
        }
        for(int i=1;i<=n;i++)
        {
            if(!v[i].empty()) cal(v[i]) ;
            if(v[i].empty())
                for(int j=0;j<=t;j++) dis[i][j]=t-j ;
            else for(int j=0,now=0 ; now<=t ; j++ )
            {
                int ri= j==v[i].size() ? t : v[i][j].x ;
                while(now<=ri) dis[i][now]=ri-now , now++ ;
                if(now==t+1) break ;
                while(now<v[i][j].y) dis[i][now]=-1 , now++ ;
            }
        }
 
        int Q ; scanf("%d",&Q) ;
        while(Q--)
        {
            int x ; scanf("%d",&x);
            int ans=-1,id ;
            for(int i=1;i<=n;i++) if(dis[i][x]>ans)
                ans=dis[id=i][x] ;
            if(ans<=0) printf("Oh, no!\n") ;
            else printf("%d %d\n",id,ans) ;
        }
    }
}