Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll MX=1e6+5;
- ll id,tree[4*MX],n,k;
- void insrt(ll x=1,ll l=1,ll r=n)
- {
- if(id<l||id>r)return;
- if(id==r&&r==l)
- {
- tree[x]++;
- return;
- }
- insrt(2*x,l,(l+r)/2);
- insrt(2*x+1,(l+r)/2 +1 , r);
- tree[x]=tree[2*x]+tree[2*x+1];
- }
- ll le,rr;
- ll srch(ll x=1,ll l=1,ll r=n)
- {
- if(le>rr)return 0;
- if(le>r||rr<l)return 0;
- if(le<=l&&r<=rr)return tree[x];
- return srch(2*x,l,(l+r)/2)+srch(2*x+1,(l+r)/2 +1 , r);
- }
- map<pair<ll,ll>,int> vis;
- int main()
- {
- cin>>n>>k;
- ll here=1,ans=1;
- for(ll i=0;i<n;i++)
- {
- id =here;
- insrt();
- ll there=(here+k);
- //cout<<there<<' '<<here<<endl;
- bool up=0;
- if(there>n)there-=n,up=1;
- if(vis[{there,here}]||vis[{here,there}])
- {
- cout<<ans<<' ';
- continue;
- }
- vis[{there,here}]=1;
- id=there;
- insrt();
- if(up)
- {
- le = here+1;
- rr = n;
- ans+=srch();
- le=1;
- rr=there-1;
- ans+=srch();
- }else
- {
- le=here+1;
- rr=there-1;
- // cout<<here<<' '<<there<<'$'<<endl;
- // cout<<le<<' '<<rr<<' '<< endl;
- ans+=srch();
- }
- cout<<++ans<<' ';
- here =there;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment