SHARE
TWEET

Untitled

a guest Aug 4th, 2015 211 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <cstring>
  6. #include <map>
  7. #include <set>
  8. #include <vector>
  9. #include <utility>
  10. #include <queue>
  11. #include <stack>
  12.  
  13. #define sd(x) scanf("%d",&x)
  14. #define sd2(x,y) scanf("%d%d",&x,&y)
  15. #define sd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  16.  
  17. #define fi first
  18. #define se second
  19. #define pb(x) push_back(x)
  20. #define mp(x,y) make_pair(x,y)
  21. #define LET(x, a)  __typeof(a) x(a)
  22. #define foreach(it, v) for(LET(it, v.begin()); it != v.end(); it++)
  23.  
  24. #define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  25. #define __ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  26.  
  27. #define tr(x) cout<<x<<endl;
  28. #define tr2(x,y) cout<<x<<" "<<y<<endl;
  29. #define tr3(x,y,z) cout<<x<<" "<<y<<" "<<z<<endl;
  30. #define tr4(w,x,y,z) cout<<w<<" "<<x<<" "<<y<<" "<<z<<endl;
  31. #define tr5(v,w,x,y,z) cout<<v<<" "<<w<<" "<<x<<" "<<y<<" "<<z<<endl;
  32. #define tr6(u,v,w,x,y,z) cout<<u<<" "<<v<<" "<<w<<" "<<x<<" "<<y<<" "<<z<<endl;
  33.  
  34. using namespace std;
  35.  
  36. const int MAXN = 1<<18;
  37.  
  38. int n, k, a[MAXN], cnt;
  39. set<int> comp;
  40. map<int, int> cord;
  41. long long tree[MAXN]; // BIT
  42.  
  43. long long ans, cur;
  44.  
  45.  
  46. long long query(int idx){
  47.     long long sum = 0;
  48.     while(idx){
  49.         sum += tree[idx];
  50.         idx -= (idx & -idx);
  51.     }
  52.     return sum;
  53. }
  54.  
  55. void update(int idx, int val){
  56.     while(idx < MAXN){
  57.         tree[idx] += val;
  58.         idx += (idx & -idx);
  59.     }
  60. }
  61.  
  62. int main(){
  63.         sd2(n,k);
  64.         for(int i = 0; i < n; i++){
  65.                 sd(a[i]);
  66.                 comp.insert(a[i]);
  67.         }
  68.        
  69.         foreach(it, comp) cord[*it] = ++cnt;
  70.        
  71.         for(int i = 0; i < n; i++) a[i] = cord[a[i]];   // Co ordinate compression
  72.  
  73.         if(k == 0){     // All subarrys are valid
  74.                 cout << ((long long) n * 1LL * (n+1)) / 2LL << "\n";
  75.                 return 0;
  76.         }
  77.        
  78.         update(a[0], 1);
  79.        
  80.         int s = 0, e = 0;
  81.         while(s < n){
  82.                 while(e < n and cur < k){
  83.                         e++;
  84.                         if(e == n) break;
  85.                        
  86.                         update(a[e],1);
  87.                         // number of elements in [s,e] - number of elements <= a[e] = #elements > a[e]
  88.                         cur += (long long) (e-s+1) - (long long) query(a[e]);
  89.                 }
  90.                
  91.                 if(cur < k) break;
  92.                
  93.                 ans += (long long) n-e; // all subarrays of the form [s,i] s.t. i >= e are valid.
  94.                                
  95.                 cur -= (long long) query(a[s]-1); // number of elements < a[s] = number of inversions due to a[s]
  96.                 update(a[s], -1);
  97.                 s++;
  98.         }
  99.         cout << ans << "\n";   
  100.                
  101.         return 0;
  102. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top