Guest User

Untitled

a guest
Jun 13th, 2017
1,422
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.74 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const long long N = 2e5 + 5;
  4. unordered_map < long long , long long > tree[4 * N];
  5. long long cnt = 0;
  6. long long n;
  7. long long k;
  8. long long a[N];
  9. long long maxi(long long a , long long b){
  10.             if(a < b){
  11.                     return b;
  12.             }
  13.             else{
  14.                     return a;
  15.             }
  16. }
  17. unordered_map < long long , long long > Merge(unordered_map < long long , long long > A , unordered_map < long long , long long >  B){
  18.             unordered_map < long long , long long > res;
  19.             for(auto j : A){
  20.                     res[(j).first] += (j).second;
  21.             }
  22.             for(auto j : B){
  23.                     res[(j).first] += (j).second;
  24.             }
  25.             return res;
  26. }
  27. void build(long long node , long long s , long long e){
  28.             if(s == e){
  29.                     tree[node][a[s]]++;
  30.                     return ;
  31.             }
  32.             long long mid = (s + e) / 2;
  33.          //   cout << "dsjdj" << endl;
  34.             build(node * 2 + 1 , s , mid);
  35.             build(node * 2 + 2 , mid + 1 , e);
  36.             tree[node] = Merge(tree[2 * node + 1] , tree[2 * node + 2]);
  37.             return ;
  38. }
  39. long long query(long long node , long long s , long long e , long long l , long long r , long long val){
  40.             if(e < l || s > r){
  41.                     return 0;
  42.             }
  43.             if(l <= s && r >= e){
  44.                     return tree[node][val];
  45.             }
  46.             long long mid = (s + e) / 2;
  47.             return query(node * 2 + 1 , s , mid , l , r , val) + query(node * 2 + 2 , mid + 1 , e , l , r , val);
  48. }
  49. int main()
  50. {
  51.             ios_base::sync_with_stdio(false);
  52.             cin.tie(0);
  53.             cout.tie(0);
  54.             cin >> n >> k;
  55.             for(long long i = 0 ; i < n ; i++){
  56.                     cin >> a[i];
  57.             }
  58.             build(0 , 0 , n - 1);
  59.             for(long long i = 1 ; i < n - 1 ; i++){
  60.                     if(k != 1){
  61.                             if(a[i] % k == 0){
  62.                                     long long fi = query(0 , 0 , n - 1 , 0 , i - 1 , a[i] / k);
  63.                                     long long se = query(0 , 0 , n - 1 , i + 1 , n - 1 , a[i] * k);
  64.                                //     cout << fi << " " << se << endl;
  65.                                     cnt += fi * se;
  66.                             }
  67.                     }
  68.                     else{
  69.                             long long fi = query(0 , 0 , n - 1 , 0 , i - 1 , a[i]);
  70.                             long long se = query(0 , 0 , n - 1 , i + 1 , n - 1 , a[i]);
  71.                             cnt += fi * se;
  72.                     }
  73.             }
  74.             cout << cnt << endl;
  75.             return 0;
  76. }
Add Comment
Please, Sign In to add comment