sacgajcvs

Untitled

Dec 19th, 2019
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.92 KB | None | 0 0
  1. /*
  2. _____ _ _ _ _
  3. |_ _| |__ ___ / \ _ __ ___| |__ _ _| |
  4. | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  5. | | | | | | __// ___ \| | | \__ \ | | | |_| | |
  6. |_| |_| |_|\___/_/ \_\_| |_|___/_| |_|\__,_|_|
  7.  
  8. */
  9. #include<bits/stdc++.h>
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. #include <ext/pb_ds/tree_policy.hpp>
  12. #define ll long long
  13. #define pb push_back
  14. #define ppb pop_back
  15. #define endl '\n'
  16. #define mii map<ll,ll>
  17. #define msi map<string,ll>
  18. #define mis map<ll, string>
  19. #define rep(i,a,b) for(ll i=a;i<b;i++)
  20. #define repr(i,a,b) for(ll i=b-1;i>=a;i--)
  21. #define trav(a, x) for(auto& a : x)
  22. #define pii pair<ll,ll>
  23. #define vi vector<ll>
  24. #define vii vector<pair<ll, ll>>
  25. #define vs vector<string>
  26. #define all(a) (a).begin(),(a).end()
  27. #define F first
  28. #define S second
  29. #define sz(x) (ll)x.size()
  30. #define hell 10000000007
  31. #define lbnd lower_bound
  32. #define ubnd upper_bound
  33.  
  34. /* For Debugging */
  35. #define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
  36. #define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
  37. #define what_is(x) cerr << #x << " is " << x << endl;
  38.  
  39. std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
  40. #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  41. #define TIME cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
  42. #define DECIMAL(n) cout << fixed ; cout << setprecision(n);
  43. #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  44. using namespace __gnu_pbds;
  45. using namespace std;
  46. #define PI 3.141592653589793
  47. #define N 200005
  48. vi v(N),a(N);
  49.  
  50. void solve()
  51. {
  52. ll n,x,d;
  53. cin>>n>>x>>d;
  54. if(d==0)
  55. {
  56. if(x==0)
  57. cout<<1<<endl;
  58. else
  59. cout<<n+1<<endl;
  60. return;
  61. }
  62. rep(i,1,n+1)
  63. {
  64. v[i]=i-1;
  65. a[i]=i-1;
  66. }
  67. if(d<0)
  68. {
  69. d=-d;
  70. x=-x;
  71. }
  72. rep(i,1,n+1)
  73. a[i]+=a[i-1];
  74. repr(i,0,n)
  75. v[i]+=v[i+1];
  76. map<ll,vector<bool>> ma;
  77. // ma[0].pb(0);
  78. // ma[0].pb(1);
  79. // ma[n*].pb(0);
  80. // ma[0].pb(1);
  81. // rep(i,0,n+1)
  82. // {
  83. // cout<<v[i]<<" ";
  84. // }
  85. // cout<<endl;
  86. // rep(i,0,n+1)
  87. // {
  88. // cout<<a[i]<<" "<<v[n+1-i]<<endl;
  89. // }
  90. // return;
  91. rep(i,0,n+1)
  92. {
  93. ma[i*x+a[i]*d].pb(0);
  94. ma[i*x+v[n+1-i]*d].pb(1);
  95. }
  96. trav(i,ma)
  97. sort(all(i.S));
  98. // trav(i,ma)
  99. // {
  100. // trav(j,i.S)
  101. // {
  102. // cout<<i.F<<" "<<j<<endl;
  103. // }
  104. // }
  105. map<ll,ll> frq,pre;
  106. ll ans=0;
  107. trav(i,ma)
  108. {
  109. rep(z,0,sz(i.S))
  110. {
  111. bool j=i.S[z];
  112. if(j==0)
  113. {
  114. frq[(i.F+hell*d)%d]++;
  115. if(frq[(i.F+hell*d)%d]==1)
  116. {
  117. pre[(i.F+hell*d)%d]=i.F;
  118. }
  119. }
  120. else
  121. {
  122. frq[(i.F+hell*d)%d]--;
  123. if(frq[(i.F+hell*d)%d]==0)
  124. {
  125. ans+=(i.F-pre[(i.F+hell*d)%d])/d+1;
  126. }
  127. }
  128. }
  129. }
  130. cout<<ans<<endl;
  131. return;
  132. }
  133. int main()
  134. {
  135. FAST
  136. int TESTS=1;
  137. // cin>>TESTS;
  138. while(TESTS--)
  139. {
  140. solve();
  141. }
  142. TIME
  143. return 0;
  144. }
Advertisement
Add Comment
Please, Sign In to add comment