fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ii pair<int, int>
  4. #define st first
  5. #define nd second
  6. #define endl "\n"
  7. #define all(v) v.begin(), v.end()
  8.  
  9. using namespace std;
  10.  
  11. const int MAXN = 1e6  + 5;
  12.  
  13. int n, k, Max[MAXN];
  14. vector<int> s[MAXN];
  15.  
  16. struct FenwickTree{
  17.     int fen[MAXN + 10];
  18.     int n = 1000005;
  19.  
  20.     void update (int u, int val){
  21.         for (; u <= n; u += (u & (-u))) fen[u] += val;
  22.     }
  23.  
  24.     int get (int u){
  25.         int ans = 0;
  26.         for (; u; u -= (u & (-u))) ans += fen[u];
  27.         return ans;
  28.     }
  29.  
  30.     int get (int l, int r){
  31.         return get(r) - get(l - 1);
  32.     }
  33.  
  34. } d;
  35.  
  36.  
  37. signed main(){
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(0);
  40.  
  41.     cin >> n >> k;
  42.  
  43.     memset(Max, -1, sizeof(Max));
  44.  
  45.     for (int i = 1; i <= n; i++){
  46.         int x, y;
  47.         cin >> x >> y;
  48.         Max[y] = max(Max[y], x);
  49.         s[y].push_back(x);
  50.  
  51.         d.update(x, 1);
  52.     }
  53.  
  54.     for (int i = (int)1e6; i >= 0; i--){
  55.         Max[i] = max(Max[i + 1], Max[i]);
  56.     }
  57.  
  58.  
  59.     ll ans = 0;
  60.     int pt = Max[1];
  61.     int furthest = Max[1];
  62.  
  63.  
  64.     for (int y = 1; y <= (int)1e6; y++){
  65.         int x = Max[y];
  66.  
  67.         if (x == -1) break;
  68.         int ins = (pt + 1 > x) ? 0 : d.get(pt + 1, x);
  69.         while (pt && ins + d.get(pt, pt) <= k){
  70.             int val = d.get(pt, pt);
  71.             if (val) furthest = pt;
  72.             ins += val;
  73.             pt--;
  74.         }
  75.  
  76.         if (ins == k){
  77.             ans += furthest - pt;
  78.         }
  79.  
  80.         for (auto x : s[y]){
  81.             d.update(x, -1);
  82.         }
  83.  
  84.  
  85.     }
  86.  
  87.     cout << ans << endl;
  88. }
  89.  
Success #stdin #stdout 0.02s 32476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/5DnB4T
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!