Advertisement
Guest User

Untitled

a guest
Jan 24th, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.44 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement