fork download 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6. #define ll long long
  7. #define pi 3.14159265358979323846 
  8. #define pb push_back
  9. #define ar array
  10. #define int long long
  11.  
  12. template<typename T, typename cmp = std::greater<T>>
  13. using pq = priority_queue<T, vector<T>, cmp>;
  14.  
  15. template<typename T, typename cmp = std::less<T>>
  16. using ordered_set = tree<T, __gnu_pbds::null_type, cmp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  17.  
  18. void chay()
  19. {
  20.     ios_base::sync_with_stdio(0);
  21.     cin.tie(0);
  22.     cout.tie(0);
  23.     #define task "SECINT"
  24.     freopen(task".INP", "r", stdin);
  25.     freopen(task".OUT", "w", stdout);
  26. }
  27.  
  28. const int N = 2e5, INF = 2e9+7;
  29. const int block = 600;
  30. const long long INFLL = 2e18+7;
  31. long long M = 1e9+7;
  32. int n, k, a[N+5], d[N+5], kq, pa[N+5], tong[N+5], sz[N+5];
  33. map<int,int> m;
  34. ar<int,2> b[N+5];
  35. ordered_set<ar<int,2>> th[N+5];
  36.  
  37. void make_set(int i)
  38. {
  39.     sz[i] = 1;
  40.     pa[i] = i;
  41.     th[i].insert({a[i], i});
  42. }
  43.  
  44. int timpa(int u)
  45. {
  46.     if (pa[u] == u) return pa[u];
  47.     return pa[u] = timpa(pa[u]);
  48. }
  49.  
  50. void hoppa(int x, int y, int mn)
  51. {
  52.     x = timpa(x);
  53.     y = timpa(y);
  54.     if (x == y) return;
  55.     if (sz[x] > sz[y]) swap(x, y);
  56.     pa[x] = y;
  57.     sz[y] += sz[x];
  58.     for (ar<int,2> r : th[x])
  59.     {
  60.         int so = r[0];
  61.         kq += th[y].order_of_key({k - so - mn, INF});
  62.     }
  63.     for (ar<int,2> r : th[x])
  64.     {
  65.         th[y].insert(r);
  66.     }
  67. }
  68.  
  69. void solve()
  70. {
  71.     cin>>n>>k;
  72.     set<ar<int,2>> s;
  73.     for (int i = 1; i <= n; i++)
  74.     {
  75.         cin>>a[i];
  76.         s.insert({a[i], i});
  77.     }
  78.  
  79.     int dem = 0;
  80.     for (ar<int,2> x : s)
  81.     {
  82.         dem++;
  83.         d[x[1]] = dem;
  84.     }
  85.  
  86.  
  87.     for (int i = 1; i <= n; i++)
  88.     {
  89.         b[i][0] = d[i];
  90.         b[i][1] = i;
  91.     }
  92.  
  93.     for (int i = 1; i <= n; i++)
  94.     {
  95.         make_set(i);
  96.     }
  97.  
  98.     sort(b+1, b+n+1, greater<ar<int,2>>());
  99.     for (int i = 1; i <= n; i++)
  100.     {
  101.         int cs = b[i][1];
  102.         if (a[cs] * 3 <= k) kq++;
  103.  
  104.         if (cs > 1 && d[cs-1] > d[cs])
  105.         {
  106.             hoppa(cs-1, cs, a[cs]);
  107.         }
  108.         if (cs < n && d[cs+1] > d[cs])
  109.         {
  110.             hoppa(cs, cs+1, a[cs]);
  111.         }
  112.     }
  113.  
  114.     cout<<kq;
  115. }
  116.  
  117. signed main ()
  118. {
  119.     chay();
  120.     int t = 1;   
  121.     //cin>>t; 
  122.     while (t--)
  123.     {
  124.         solve();
  125.     }
  126.  
  127.     return 0;
  128. }
Success #stdin #stdout 0.03s 26304KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Xhq5ZW
language:
C++14 (gcc 8.3)
created:
5 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!