1 /* 2     题意：n个时刻点，m次时光穿梭，告诉的起点和终点，q次询问，每次询问t时刻t之前有多少时刻点是可以通过两种不同的路径到达 3     思维：对于当前p时间，从现在到未来穿越到过去的是有效的值，排个序，从大到小询问，那么之前添加的穿越点都是有效的， 4         用multiset保存。比赛时想到了排序，但是无法用线段树实现查询，stl大法好！ 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 #include 
         
          11 using namespace std;12 13 const int MAXN = 1e5 + 10;14 const int INF = 0x3f3f3f3f;15 struct Year {16     int u, v;17     bool operator < (const Year &r) const   {18         return u > r.u;19     }20 }y[MAXN];21 struct Query   {22     int p, id;23     bool operator < (const Query &r) const  {24         return p > r.p;25     }26 }q[MAXN];27 int ans[MAXN];28 int a[3];29 int n, m, l;30 31 int main(void)  {       //ZOJ Monthly, July 2015 - H Twelves Monkeys32     //freopen ("H.in", "r", stdin);33 34     while (scanf ("%d%d%d", &n, &m, &l) == 3)   {35         for (int i=1; i<=m; ++i)    {36             scanf ("%d%d", &y[i].u, &y[i].v);37         }38         for (int i=1; i<=l; ++i)    {39             scanf ("%d", &q[i].p);  q[i].id = i;40         }41 42         sort (y+1, y+1+m);  sort (q+1, q+1+l);43         multiset
          
            S; int j = 1;44 for (int i=1; i<=l; ++i) {45 while (j <= m && y[j].u >= q[i].p) {46 S.insert (y[j].v); j++;47 }48 multiset
           
            ::iterator it; int cnt = 0;49 for (it=S.begin (); it!=S.end (); ++it) {50 a[++cnt] = *(it); if (cnt == 2) break;51 }52 if (cnt == 2 && a[2] <= q[i].p) ans[q[i].id] = q[i].p - a[2];53 else ans[q[i].id] = 0;54 } 55 for (int i=1; i<=l; ++i)56 printf ("%d\n", ans[i]);57 }58 59 return 0;60 }