Advertisement
jeff69

Untitled

Jan 15th, 2017
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.47 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const ll MX=1e6+5;
  6. ll id,tree[4*MX],n,k;
  7. void insrt(ll x=1,ll l=1,ll r=n)
  8. {
  9. if(id<l||id>r)return;
  10. if(id==r&&r==l)
  11. {
  12. tree[x]++;
  13. return;
  14. }
  15. insrt(2*x,l,(l+r)/2);
  16. insrt(2*x+1,(l+r)/2 +1 , r);
  17. tree[x]=tree[2*x]+tree[2*x+1];
  18. }
  19. ll le,rr;
  20. ll srch(ll x=1,ll l=1,ll r=n)
  21. {
  22. if(le>rr)return 0;
  23. if(le>r||rr<l)return 0;
  24. if(le<=l&&r<=rr)return tree[x];
  25. return srch(2*x,l,(l+r)/2)+srch(2*x+1,(l+r)/2 +1 , r);
  26. }
  27. map<pair<ll,ll>,int> vis;
  28. int main()
  29. {
  30. cin>>n>>k;
  31. ll here=1,ans=1;
  32.  
  33. for(ll i=0;i<n;i++)
  34. {
  35.  
  36. id =here;
  37. insrt();
  38. ll there=(here+k);
  39. //cout<<there<<' '<<here<<endl;
  40. bool up=0;
  41. if(there>n)there-=n,up=1;
  42. if(vis[{there,here}])
  43. {
  44. cout<<ans<<' ';
  45. continue;
  46. }
  47. vis[{there,here}]=1;
  48.  
  49. id=there;
  50. insrt();
  51.  
  52. if(up)
  53. {
  54. le = here+1;
  55. rr = n;
  56. ans+=srch();
  57. le=1;
  58. rr=there-1;
  59. ans+=srch();
  60. }else
  61. {
  62. le=here+1;
  63. rr=there-1;
  64. // cout<<here<<' '<<there<<'$'<<endl;
  65. // cout<<le<<' '<<rr<<' '<< endl;
  66. ans+=srch();
  67.  
  68. }
  69.  
  70. cout<<++ans<<' ';
  71. here =there;
  72. }
  73. return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement