fork download 
  1. #include "iostream"
  2. #include "algorithm"
  3. #include "vector"
  4. #include "set"
  5. #include "map"
  6. #include "cstring"
  7. #include "string"
  8. #include "vector"
  9. #include "cassert"
  10. #include "queue"
  11. #include "cstdio"
  12. #include "cstdlib"
  13. #include "ctime"
  14. #include "cmath"
  15. #include "bitset"
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef pair < int, int > ii;
  21.  
  22. const int N = 1e5 + 5;
  23.  
  24. int n, d, k;
  25. ii a[N];
  26. int ans[N];
  27.  
  28. vector < int > up[N];
  29.  
  30. class tree{ public:
  31.     vector < int > vs, fen;
  32.     void add(int x) {
  33.         vs.push_back(x);
  34.     }
  35.     void init() {
  36.         sort(vs.begin(), vs.end());
  37.         vs.resize(unique(vs.begin(), vs.end()) - vs.begin());
  38.         fen.resize(vs.size() + 1, n + 1);
  39.     }
  40.     int id(int x) {
  41.         return upper_bound(vs.begin(), vs.end(), x) - vs.begin();
  42.     }
  43.     int get(int x) {
  44.         int res = n + 1;
  45.         for(x = id(x); x; x -= x & -x)
  46.             res = min(res, fen[x]);
  47.         return res;
  48.     }
  49.     void upd(int x, int v) {
  50.         for(x = id(x); x < fen.size(); x += x & -x)
  51.             fen[x] = min(fen[x], v);
  52.     }
  53. };
  54.  
  55. tree data[N << 1];
  56.  
  57. void addT(int i) {
  58.     int x = a[i].first + N;
  59.     while(x >= 1) {
  60.         data[x].add(a[i].second);
  61.         x >>= 1;
  62.     }
  63. }
  64.  
  65. void updT(int i) {
  66.     int x = a[i].first + N;
  67.     while(x >= 1) {
  68.         data[x].upd(a[i].second, i);
  69.         x >>= 1;
  70.     }
  71. }
  72.  
  73. int getT(int x, int y) {
  74.     int res = n + 1;
  75.     for(int l = x + N, r = y + N; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
  76.         if(l & 1) res = min(res, data[l].get(y));
  77.         if(~r & 1) res = min(res, data[r].get(y));
  78.     }
  79.     return res;
  80. }
  81.  
  82. int go(int l, int r) {
  83.     int i = getT(l, r);
  84.     if(i > n)
  85.         return 0;
  86.     return a[i].second - a[i].first + 1 + go(l, a[i].first - 1) + go(a[i].second + 1, r);
  87. }
  88.  
  89. int main () {
  90.  
  91.     scanf("%d %d %d", &n, &d, &k);
  92.  
  93.     for(int i = 1; i <= n; i++) {
  94.         scanf("%d %d", &a[i].first, &a[i].second);
  95.         up[a[i].second - a[i].first + 1].push_back(i);
  96.     }
  97.  
  98.     for(int i = 1; i <= n; i++)
  99.         addT(i);
  100.  
  101.     for(int i = 1; i < N + N; i++)
  102.         data[i].init();
  103.  
  104.     for(int len = d; len >= 1; len--) {
  105.         if(up[len].empty()) {
  106.             ans[len] = ans[len + 1];
  107.             continue;
  108.         }
  109.         for(auto i : up[len]) {
  110.             updT(i);
  111.         }
  112.         ans[len] = go(1, d);
  113.     }
  114.  
  115.     for(int i = 1; i <= k; i++) {
  116.         int x;
  117.         scanf("%d", &x);
  118.         printf("%d\n", ans[x]);
  119.     }
  120.  
  121.     return 0;
  122.  
  123. }
Success #stdin #stdout 0.02s 13528KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/dN3HVz
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!