Advertisement
jeff69

Untitled

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