Guest User

Untitled

a guest
Feb 4th, 2017
101
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define maxn 300009
  3. #define inf 1000000007
  4. #define llinf 1000000000000000007
  5. #define ff first
  6. #define ss second
  7. #define mp make_pair
  8. #define pb push_back
  9. #define mid(a,b) (a+b)/2
  10. #define endl "\n"
  11. #define sz size()
  12. #define MOD 1000000007
  13. #define M 100000
  14. #define pii pair<int,int>
  15. #define all(x) x.begin(),x.end()
  16. #define tr(i, c) for(typeof((c).begin()) i = (c).begin(); i!=(c).end(); i++)
  17. using namespace std;
  18. typedef long long ll;
  19. //priority_queue < pii, vector< pii >, greater< pii > > Q;
  20.  
  21.  
  22.  
  23. int s[maxn*3], a[maxn];
  24.  
  25. void build(int nd, int l, int r){
  26. if(l == r){
  27. s[nd] = a[l];
  28. return;
  29. }
  30. build((nd<<1), l, mid(l, r));
  31. build(((nd<<1)|1), mid(l, r)+1, r);
  32. s[nd] = s[(nd<<1)] + s[((nd<<1)|1)];
  33. }
  34. void upd(int nd, int l, int r, int x){
  35. if(l == r){
  36. s[nd] = 1;
  37. return;
  38. }
  39. if(x <= mid(l, r))
  40. upd((nd<<1), l, mid(l, r), x);
  41. else
  42. upd(((nd<<1)|1), mid(l, r)+1, r, x);
  43. s[nd] = s[(nd<<1)] + s[((nd<<1)|1)];
  44. }
  45.  
  46. int get(int nd, int l, int r, int x, int y){
  47. if(l > y or r < x)
  48. return 0;
  49. if(l >= x && r <= y)
  50. return s[nd];
  51. return get((nd<<1), l, mid(l, r), x, y) + get(((nd<<1)|1), mid(l, r)+1, r, x, y);
  52. }
  53.  
  54. int main(){
  55. ios_base::sync_with_stdio(false);
  56. cin.tie(NULL);
  57. int n, d, ans = 0, pos;
  58. cin>>n>>d;
  59. for(int i=1; i<=n; i++)
  60. cin>>a[i];
  61. build(1, 1, n);
  62. for(int i=1; i<n; i++){
  63. pos = min(n, i+d);
  64. if(get(1, 1, n, i+1, pos) == 0){
  65. upd(1, 1, n, pos);
  66. ans++;
  67. }
  68. }
  69. cout<<ans<<endl;
  70.  
  71.  
  72. return 0;
  73. }
RAW Paste Data