Advertisement
Guest User

Untitled

a guest
Nov 29th, 2014
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.50 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cstdio>
  6. #include<vector>
  7. #include<cmath>
  8. #include<queue>
  9. #include<stack>
  10. #include<deque>
  11. #include<map>
  12. #include<set>
  13. #define MAX(a,b) (a>b?a:b)
  14. #define MIN(a,b) (a<b?a:b)
  15. #define UP upper_bound
  16. #define LB lower_bound
  17. #define LL long long
  18. #define Pi 3.14159265358
  19. #define si size()
  20. #define en end()
  21. #define be begin()
  22. #define fi first
  23. #define se second
  24. #define pb push_back
  25. #define mp make_pair
  26. #define ii set<int>::iterator
  27. using namespace std;
  28. void build(int ind, int L, int R)
  29. {
  30. if(L==R)
  31. {
  32. tree[ind].st=0;
  33. tree[ind].en=0;
  34. tree[ind].mx=0;
  35. tree[ind].bl=1;
  36. return;
  37. }
  38. build(2*ind,L,(L+R)/2);
  39. build(2*ind+1,(L+R)/2+1,R);
  40. if(tree[2*ind].bl^tree[2*ind+1].bl){ tree[ind].bl=0; goto done; }
  41. else
  42. {
  43. int delta=min(C-tree[2*ind].mx,max(tree[2*ind+1].st-tree[2*ind].en+a[(R+L)/2+1]));
  44. if(max(C,tree[2*ind].en+delta)<tree[2*ind+1].st){ tree[ind].bl=0; goto done; }
  45.  
  46. }
  47. done: ;
  48. }
  49. main(){
  50. cin>>n>>C;
  51. for(i=1;i<=n;i++)
  52. {
  53. scanf("%d",&a[i]);
  54. a[i+n]=a[i];
  55. }
  56. for(i=1;i<=n;i++)
  57. {
  58. scanf("%d",&b[i]);
  59. b[i+n]=b[i];
  60. }
  61. build(1,1,k);
  62. for(i=1;i<=n;i++)
  63. {
  64. l=i; r=n+i;
  65. Res=Solve(1,1,k);
  66. if(Res.bl)ans++;
  67. }
  68. cout<<ans;
  69. system("pause");
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement