Advertisement
deushiro

Untitled

Jan 9th, 2020
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6. #include <set>
  7. #include <map>
  8. #include <list>
  9. #include <time.h>
  10. #include <math.h>
  11. #include <random>
  12. #include <deque>
  13. #include <queue>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include <iomanip>
  18. #include <bitset>
  19. #include <sstream>
  20. #include <chrono>
  21. #include <cstring>
  22.  
  23. using namespace std;
  24.  
  25. typedef unsigned long long ll;
  26.  
  27. int main()
  28. {
  29.     ios_base::sync_with_stdio(false);
  30.     cin.tie(0);
  31.     cout.tie(0);
  32.     int n, k;
  33.     cin >> n >> k;
  34.     vector<pair<ll,ll>> m;
  35.     vector<ll> a(n);
  36.     ll ans = 0;
  37.     for(int i = 0; i < n; ++i){
  38.         cin >> a[i];
  39.     }
  40.     sort(a.begin(), a.end());
  41.     for(int i = 0; i < n; ++i){
  42.         if(m.size() == 0 || m.back().first != a[i]){
  43.             m.push_back({a[i], 1});
  44.         }
  45.         else{
  46.             m.back().second++;
  47.         }
  48.     }
  49.     n = m.size();
  50.     for(int i = 0; i < n; ++i){
  51.         if(m[i].second > 2){
  52.             ++ans;
  53.         }
  54.     }
  55.     int i = 0;
  56.     int j = 0;
  57.     while(i < n){
  58.         while(j + 1 < n && m[i].first * k >= m[j + 1].first){
  59.             ++j;
  60.         }
  61.         if(j - i + 1 >= 3 && i + 3 <= n)
  62.             ans += 1LL * 3 * (j - i - 1) * (j - i);
  63.         //cout << i << " " << j << endl;
  64.         ++i;
  65.     }
  66.     i = 0;
  67.     j = 0;
  68.     int x = 0;
  69.     while(i < n){
  70.         while(j + 1 < n && m[i].first * k >= m[j + 1].first){
  71.             ++j;
  72.         }
  73.         while(x + 1 < n && m[x].first * k < m[i].first){
  74.             ++x;
  75.         }
  76.         if(m[i].second > 1)
  77.             ans += 1LL * 3 * (j - x);
  78.         ++i;
  79.     }
  80.     cout << ans * 1LL << endl;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement