Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- _____ _ _ _ _
- |_ _| |__ ___ / \ _ __ ___| |__ _ _| |
- | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
- | | | | | | __// ___ \| | | \__ \ | | | |_| | |
- |_| |_| |_|\___/_/ \_\_| |_|___/_| |_|\__,_|_|
- */
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define ll long long
- #define pb push_back
- #define ppb pop_back
- #define endl '\n'
- #define mii map<ll,ll>
- #define msi map<string,ll>
- #define mis map<ll, string>
- #define rep(i,a,b) for(ll i=a;i<b;i++)
- #define repr(i,a,b) for(ll i=b-1;i>=a;i--)
- #define trav(a, x) for(auto& a : x)
- #define pii pair<ll,ll>
- #define vi vector<ll>
- #define vii vector<pair<ll, ll>>
- #define vs vector<string>
- #define all(a) (a).begin(),(a).end()
- #define F first
- #define S second
- #define sz(x) (ll)x.size()
- #define hell 10000000007
- #define lbnd lower_bound
- #define ubnd upper_bound
- /* For Debugging */
- #define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
- #define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
- #define what_is(x) cerr << #x << " is " << x << endl;
- std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
- #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
- #define TIME cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
- #define DECIMAL(n) cout << fixed ; cout << setprecision(n);
- #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- using namespace __gnu_pbds;
- using namespace std;
- #define PI 3.141592653589793
- #define N 200005
- vi v(N),a(N);
- void solve()
- {
- ll n,x,d;
- cin>>n>>x>>d;
- if(d==0)
- {
- if(x==0)
- cout<<1<<endl;
- else
- cout<<n+1<<endl;
- return;
- }
- rep(i,1,n+1)
- {
- v[i]=i-1;
- a[i]=i-1;
- }
- if(d<0)
- {
- d=-d;
- x=-x;
- }
- rep(i,1,n+1)
- a[i]+=a[i-1];
- repr(i,0,n)
- v[i]+=v[i+1];
- map<ll,vector<bool>> ma;
- // ma[0].pb(0);
- // ma[0].pb(1);
- // ma[n*].pb(0);
- // ma[0].pb(1);
- // rep(i,0,n+1)
- // {
- // cout<<v[i]<<" ";
- // }
- // cout<<endl;
- // rep(i,0,n+1)
- // {
- // cout<<a[i]<<" "<<v[n+1-i]<<endl;
- // }
- // return;
- rep(i,0,n+1)
- {
- ma[i*x+a[i]*d].pb(0);
- ma[i*x+v[n+1-i]*d].pb(1);
- }
- trav(i,ma)
- sort(all(i.S));
- // trav(i,ma)
- // {
- // trav(j,i.S)
- // {
- // cout<<i.F<<" "<<j<<endl;
- // }
- // }
- map<ll,ll> frq,pre;
- ll ans=0;
- trav(i,ma)
- {
- rep(z,0,sz(i.S))
- {
- bool j=i.S[z];
- if(j==0)
- {
- frq[(i.F+hell*d)%d]++;
- if(frq[(i.F+hell*d)%d]==1)
- {
- pre[(i.F+hell*d)%d]=i.F;
- }
- }
- else
- {
- frq[(i.F+hell*d)%d]--;
- if(frq[(i.F+hell*d)%d]==0)
- {
- ans+=(i.F-pre[(i.F+hell*d)%d])/d+1;
- }
- }
- }
- }
- cout<<ans<<endl;
- return;
- }
- int main()
- {
- FAST
- int TESTS=1;
- // cin>>TESTS;
- while(TESTS--)
- {
- solve();
- }
- TIME
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment