CodeForces1000C-白红宇

CodeForces1000C

阅读量：5290 次

发布时间：2019-06-14

本文共 908 字，大约阅读时间需要 3 分钟。

本来以为是道水题,然后我看到了数据范围,当时就有点方,觉得这题难死了

然鹅,我冷静了一会儿发现,离散化一下好像就变成了真水题,但是...排序离散化我搞了半天不知道哪里有毛病...于是....

抱着试试的心态我试了试 \(map\) , 然后就一帆风顺地 \(AC\) 了

不考虑高达 \(10^{18}\) 的区间范围的话,就只需要做一遍差分,然后做一遍前缀和统计答案就好了.

离散化之后也一样做.

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #define int long longusing std::map ;const int N = 2e5 + 100 ;map < int , int > mk ;int n , ans[N] ;signed main () { scanf ("%lld" , & n ) ; for (int i = 1 , u , v ; i <= n ; ++ i) { scanf ("%lld%lld" , & u , & v ) ; ++ mk[u] ; -- mk[v+1] ; } int cnt = 0 , last = 0 ; for (auto it = mk.begin () ; it != mk.end () ; ++ it) { ans[cnt] += ( it->first - last ) ; last = it->first ; cnt += it->second ; } for (int i = 1 ; i <= n ; ++ i) printf ("%lld " , ans[i] ) ; system ("pause") ; return 0 ;}