SHARE
TWEET

Untitled

a guest Jan 24th, 2019 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <map>
  3. #include <set>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <iomanip>
  7. #include <vector>
  8. #include <queue>
  9. #include <fstream>
  10. using namespace std;
  11. void stress();
  12. int main()
  13. {
  14.     ios::sync_with_stdio(0);
  15.     cin.tie(0);
  16. //    srand(time(0));
  17.     stress();
  18. }
  19.  
  20. #define int long long
  21.  
  22. void stress()
  23. {
  24.     ifstream cin("game.in");
  25.     ofstream cout("game.out");
  26.     int n,k;
  27.     cin >> n >> k;
  28.     vector<int> a(n);
  29.     vector<int> cnt(n);
  30.     map<int,int> m;
  31.     for (int i = 0; i<n; i++) {
  32.         cin >> a[i];
  33.         m[a[i]]++;
  34.     }
  35.     map<int,int> was;
  36.     sort(a.begin(),a.end());
  37.     vector<pair<int,int>> b;
  38.     int ans = 0;
  39.     for(int j = 0; j<n; j++)
  40.     {
  41.         if (was[a[j]])
  42.             continue;
  43.         was[a[j]] = 1;
  44.         b.push_back({a[j],m[a[j]]});
  45.         if (b.back().second>2)
  46.             ans++;
  47.     }
  48.     int r = 0;
  49.     for (int i = 0; i<b.size(); i++) {
  50.         while (r < b.size() && b[r].first <= b[i].first * k) {
  51.             r++;
  52.         }
  53.         r--;
  54.         int len = r - i;
  55.         ans += 3 * len * (len - 1);
  56.         if (b[i].second>1)
  57.         {
  58.             ans+=3*len;
  59.         }
  60.     }
  61.     int l = b.size()-1;
  62.     for (int i = b.size()-1; i>=0; i--)
  63.     {
  64.         while (l>=0 && b[l].first*k>=b[i].first)
  65.             l--;
  66.         l++;
  67.         int len = i-l;
  68.         if (b[i].second>1)
  69.             ans+=3*len;
  70.     }
  71.     cout << ans;
  72.  
  73. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top