fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "gen"
  33. /*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */
  34.  
  35. const int MOD = 1e9 + 7;
  36. const int inf = 1e9 + 27092008;
  37. const ll INF = 1e18 + 27092008;
  38. const int N = 2e5 + 5;
  39. int n, a[N], ans[N];
  40. ll K;
  41. vector<int> compress;
  42.  
  43. struct BIT {
  44.     int ft[N], sum = 0;
  45.     vector<ii> history;
  46.     void update(int x, int val, bool rem) {
  47.         if (rem) history.emplace_back(x, val);
  48.         sum += val;
  49.         for(; x <= n; x += x & -x) ft[x] += val;
  50.     }
  51.  
  52.     int get(int x) {
  53.         int ans = 0;
  54.         for(; x; x -= x & -x) ans += ft[x];
  55.         return ans;
  56.     }
  57.  
  58.     void snap_shot() {
  59.         history.emplace_back(-1, -1);
  60.     }
  61.  
  62.     void roll_back() {
  63.         while(!history.empty()) {
  64.             ii tmp = history.back(); history.pop_back();
  65.             if (tmp.fi == -1) break;
  66.             update(tmp.fi, -tmp.se, false);
  67.         }
  68.     }
  69. } fenL, fenR;
  70. ll inv = 0;
  71.  
  72. void add(ll &x, ll y) {
  73.     x = min(INF, x + y);
  74. }
  75.  
  76. void DnC(int qryL, int qryR, int ansL, int ansR) {
  77.     if (qryL > qryR) return;
  78.     int qryM = (qryL + qryR) >> 1, ansM = max(ansL, qryM + 1);
  79.     ll tmp = inv;
  80.     fenL.snap_shot();
  81.  
  82.     FOR(i, qryL, qryM) {
  83.         fenL.update(a[i], +1, true);
  84.         add(inv, fenL.sum - fenL.get(a[i]));
  85.         add(inv, fenR.get(a[i] - 1));
  86.     }
  87.  
  88.     if (inv > K) {
  89.         inv = tmp;
  90.         ans[qryM] = n + 1;
  91.         fenL.roll_back();
  92.         DnC(qryL, qryM - 1, ansL, ansR);
  93.         return;
  94.     }
  95.  
  96.     fenR.snap_shot();
  97.  
  98.     ll bef = inv;
  99.     FORR(i, ansR, max(ansL, qryM + 1)) {
  100.         fenR.update(a[i], +1, true);
  101.         inv += fenR.get(a[i] - 1);
  102.         inv += fenL.sum - fenL.get(a[i]);
  103.         if (inv > K) {
  104.             ansM = i + 1;
  105.             break;
  106.         }
  107.     }
  108.  
  109.     if (ansM == n + 1) {
  110.         fenR.roll_back();
  111.         fenL.roll_back();
  112.         inv = tmp;
  113.         DnC(qryL, qryM - 1, ansL, ansR);
  114.         return;
  115.     }
  116.  
  117.     ans[qryM] = ansM;
  118.     inv = bef;
  119.  
  120.     fenR.roll_back();
  121.     DnC(qryM + 1, qryR, ansM, ansR);
  122.  
  123. //    if (qryL == 1 && qryR == 5) {
  124. //        cout << tmp << ' '  << ansM << '\n';
  125. //        FOR(i, 1, n) assert(fenR.ft[i] == 0);
  126. //    }
  127.     inv = tmp;
  128.     fenL.roll_back();
  129.     fenR.snap_shot();
  130.     FORR(i, ansR, ansM + 1) {
  131.         inv += fenL.sum - fenL.get(a[i]);
  132.         inv += fenR.get(a[i] - 1);
  133.         fenR.update(a[i], +1, true);
  134.     }
  135.     DnC(qryL, qryM - 1, ansL, ansM);
  136.     fenR.roll_back();
  137. }
  138.  
  139. void init(void) {
  140.     cin >> n >> K;
  141.     FOR(i, 1, n) cin >> a[i], compress.pb(a[i]);
  142.     sort(all(compress));
  143.     FOR(i, 1, n) a[i] = upper_bound(all(compress), a[i]) - compress.begin();
  144. }
  145.  
  146. void process(void) {
  147.     FOR(i, 1, n) ans[i] = n + 1;
  148.     DnC(1, n, 1, n);
  149.     ll res = 0;
  150.     FOR(i, 1, n) res += n + 1 - ans[i];
  151.     cout << res;
  152. }
  153.  
  154. int main() {
  155.     ios_base::sync_with_stdio(0);
  156.     cin.tie(0); cout.tie(0);
  157.     if (fopen(task".inp", "r")) {
  158.         freopen(task".inp", "r", stdin);
  159.         freopen(task".out", "w", stdout);
  160.     }
  161.     int tc = 1;
  162. //    cin >> tc;
  163.     while(tc--) {
  164.         init();
  165.         process();
  166.     }
  167.     return 0;
  168. }
  169.  
Success #stdin #stdout 0.01s 5644KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/D0RgLA
language:
C++14 (gcc 8.3)
created:
4 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!