fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define  fi first
  3. #define  se second
  4.  
  5. using namespace std;
  6. using pii = pair <int, int>;
  7. const int N = 1e5;
  8. struct Fenwisk {
  9.         vector <long long> bit;
  10.         int n;
  11.         Fenwisk (int _n) {
  12.             n = _n;
  13.             bit.assign (n+3, 0);
  14.         }
  15.         long long get (int x) {
  16.             long long res = 0;
  17.             for (;x <= n; x += x&-x) res += bit [x];
  18.             return res;
  19.         }
  20.         void upd (int x, int val) {
  21.             for (;x > 0; x -= x&-x) bit [x] += val;
  22.         }
  23. };
  24. struct Fenwisk2 {
  25.         vector <long long> bit;
  26.         int n;
  27.         Fenwisk2 (int _n) {
  28.             n = _n;
  29.             bit.assign (n+3, 0);
  30.         }
  31.         long long get (int x) {
  32.             long long res = 0;
  33.             for (;x > 0; x -= x&-x) res += bit [x];
  34.             return res;
  35.         }
  36.         void upd (int x, int val) {
  37.             for (;x <= n; x += x&-x) bit [x] += val;
  38.         }
  39. };
  40. int main () {
  41.         ios_base::sync_with_stdio (false);
  42.         cin.tie (0);         cout.tie (0); 
  43.         long long K;
  44.         int n; cin >> n >> K;
  45.         vector <int> a (n+5);
  46.         for (int i=1; i<=n; i++) cin >> a [i];
  47.  
  48.         vector <int> val = a;
  49.         sort (val.begin (), val.end ());
  50.         val.erase (unique (val.begin (), val.end ()), val.end ());
  51.         auto idx = [&](int x) {
  52.             return lower_bound (val.begin (), val.end (), x) - val.begin () + 1;
  53.         };
  54.         for (int i=1; i<=n; i++ )
  55.             a [i] = idx (a [i]);
  56.         Fenwisk fw (val.size ());
  57.         Fenwisk2 fen (val.size ());
  58.  
  59.         long long ans = 0, res = 0;
  60.         int r = 2;
  61.         for (int i=n; i>=2; i--) {
  62.             res += fen.get (a [i]-1);
  63.             fen.upd (a [i],1);
  64.         }
  65.         long long full = res + fen.get (a [1]-1);
  66.         if (full <= K) return cout << 1LL*n*(n-1)/2, 0;
  67.         for (int i=1; i<=n; i++) {
  68.             res += fw.get (a [i]+1);
  69.             res += fen.get (a [i]-1);
  70.             fw.upd (a [i], 1);
  71.             while (res > K && r <= n) {
  72.                 fen.upd (a [r], -1);
  73.                 res -= fw.get (a [r]+1);
  74.                 res -= fen.get (a [r]-1);
  75.                 r++;
  76.             }
  77.             ans += n-r+1;
  78.         }
  79.         cout << ans;
  80.         return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6i9utp
language:
C++14 (clang 8.0)
created:
6 days 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!