fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<int, int> ii;
  5. typedef vector<ii> vii;
  6. typedef vector<int> vi;
  7. typedef vector<ll> vll;
  8. #define FOR(i,n) for (i = 0; i < n; ++i)
  9. #define FORK(i,k,n) for (i = k; i <= n; ++i)
  10. #define FORR(i,k,n) for (i = k; i >= n; --i)
  11.  
  12. #define re(a,b)   memset(a,b,sizeof(a))
  13. #define sz(a)      (int)(a.size())
  14. #define MIN(a,b)     (a) = min((a),(b))
  15. #define MAX(a,b)     (a) = max((a),(b))
  16. #define input(in)    freopen(in,"r",stdin)
  17. #define output(out)  freopen(out,"w",stdout)
  18. #define ALL(a)       a.begin(),a.end()
  19. #define RALL(a)      a.rbegin(),a.rend()
  20. #define LEN(a)       (int)(a.length())
  21.  
  22. #define FIN(x)       freopen(x,"r",stdin)
  23. #define FOUT(x)      freopen(x,"w",stdout)
  24. #define FCLOSE       {fclose(stdin); fclose(stdout);}
  25.  
  26. #define fi           first
  27. #define se           second
  28. #define pb           push_back
  29. #define mp           make_pair
  30. #define  M           1000010
  31. #define INF          1001001001
  32.  
  33. ll visit[M];// for counting the elements
  34. void update(ll i,ll v,ll b[],ll n)
  35. {
  36.     for(; i <=n; i += i&-i)
  37.         b[i] += v;
  38. }
  39. ll query(ll x,ll b[])
  40. {
  41.      ll sum = 0;
  42.      for(; x > 0; x -= x&-x)
  43.         sum += b[x];
  44.      return sum;
  45. }
  46. template<class T> 	//fast I/O operations
  47. inline void inp(T &p) {
  48.     p=0; register char ch=0;
  49.     while(ch<'0' or ch>'9') {ch=getchar();}
  50.     while(ch>='0' and ch<='9') {p=(p<<1)+(p<<3)+ch-'0'; ch=getchar();}
  51. }
  52. int main()
  53. {
  54.    // ios_base::sync_with_stdio(false);cin.tie(0);
  55.     ll i,j,n,x,y,k;
  56.     inp(n);
  57.     inp(k);
  58.     ll pi[n]={0},t[n];
  59.     ll ans=0;
  60.     vector<ll> a;
  61.     FOR(i,n)
  62.     {
  63.         inp(t[i]);
  64.         a.pb(t[i]);
  65.     }
  66.     FOR(i,M)
  67.     visit[i]=0;
  68.      sort(t,t+n);
  69.         FOR(i,n)
  70.         {
  71.             a[i]=lower_bound(t,t+n,a[i])-t+1;
  72.         }
  73.     for(i=n-1;i>=0;i--)
  74.     {
  75.       //   cout << a[i] << " ";
  76.          pi[i]=query(M-1,visit)-query(a[i],visit);
  77.          update(a[i],1,visit,M);
  78.      }
  79.     sort(pi,pi+n);
  80.     for(i=n-1;i>=0;i--)
  81.     {
  82.      //   cout << i << " " << pi[i] << " " << k-pi[i]  << "\n";
  83.         j=lower_bound(pi,pi+n,k-pi[i])-pi;
  84.       //  cout << j << "\n";
  85.         if(j!=n && j<i)
  86.         ans+=i-j;
  87.     }
  88.     printf("%d",ans);
  89.     return 0;
  90. }
  91.  
Time limit exceeded #stdin #stdout 5s 23056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vXHQV1
language:
C++ (gcc 8.3)
created:
7 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!