fork download
  1. #pragma comment(linker, "/stack:640000000")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const double EPS = 1e-9;
  6. const int INF = 0x7f7f7f7f;
  7. const double PI=acos(-1.0);
  8.  
  9. #define READ(f) freopen(f, "r", stdin)
  10. #define WRITE(f) freopen(f, "w", stdout)
  11. #define MP(x, y) make_pair(x, y)
  12. #define PB(x) push_back(x)
  13. #define rep(i,n) for(int i = 1 ; i<=(n) ; i++)
  14. #define repI(i,n) for(int i = 0 ; i<(n) ; i++)
  15. #define FOR(i,L,R) for (int i = (int)(L); i <= (int)(R); i++)
  16. #define ROF(i,L,R) for (int i = (int)(L); i >= (int)(R); i--)
  17. #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
  18. #define ALL(p) p.begin(),p.end()
  19. #define ALLR(p) p.rbegin(),p.rend()
  20. #define SET(p) memset(p, -1, sizeof(p))
  21. #define CLR(p) memset(p, 0, sizeof(p))
  22. #define MEM(p, v) memset(p, v, sizeof(p))
  23. #define getI(a) scanf("%d", &a)
  24. #define getII(a,b) scanf("%d%d", &a, &b)
  25. #define getIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
  26. #define getL(a) scanf("%lld",&a)
  27. #define getLL(a,b) scanf("%lld%lld",&a,&b)
  28. #define getLLL(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
  29. #define getC(n) scanf("%c",&n)
  30. #define getF(n) scanf("%lf",&n)
  31. #define getS(n) scanf("%s",n)
  32. #define bitCheck(N,in) ((bool)(N&(1<<(in))))
  33. #define bitOff(N,in) (N&(~(1<<(in))))
  34. #define bitOn(N,in) (N|(1<<(in)))
  35. #define bitFlip(a,k) (a^(1<<(k)))
  36. #define bitCount(a) __builtin_popcount(a)
  37. #define bitCountLL(a) __builtin_popcountll(a)
  38. #define bitLeftMost(a) (63-__builtin_clzll((a)))
  39. #define bitRightMost(a) (__builtin_ctzll(a))
  40. #define iseq(a,b) (fabs(a-b)<EPS)
  41. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  42. #define vi vector < int >
  43. #define vii vector < vector < int > >
  44. #define pii pair< int, int >
  45. #define ff first
  46. #define ss second
  47. #define ll long long
  48. #define ull unsigned long long
  49. #define POPCOUNT __builtin_popcount
  50. #define POPCOUNTLL __builtin_popcountll
  51. #define RIGHTMOST __builtin_ctzll
  52. #define LEFTMOST(x) (63-__builtin_clzll((x)))
  53.  
  54. template< class T > inline T gcd(T a, T b) { return (b) == 0 ? (a) : gcd((b), ((a) % (b))); }
  55. template< class T > inline T lcm(T a, T b) { return ((a) / gcd((a), (b)) * (b)); }
  56. template <typename T> string NumberToString ( T Number ) { ostringstream ss; ss << Number; return ss.str(); }
  57.  
  58. #ifdef dipta007
  59. #define debug(args...) {cerr<<"Debug: "; dbg,args; cerr<<endl;}
  60. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  61. template <typename Arg1>
  62. void __f(const char* name, Arg1&& arg1){
  63. cerr << name << " : " << arg1 << std::endl;
  64. }
  65. template <typename Arg1, typename... Args>
  66. void __f(const char* names, Arg1&& arg1, Args&&... args){
  67. const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  68. }
  69. #else
  70. #define debug(args...) /// Just strip off all debug tokens
  71. #define trace(...) ///yeeeee
  72. #endif
  73.  
  74. struct debugger{
  75. template<typename T> debugger& operator , (const T& v){
  76. cerr<<v<<" ";
  77. return *this;
  78. }
  79. }dbg;
  80. ///****************** template ends here ****************
  81. int t,n,m;
  82.  
  83.  
  84. #define mx 100004
  85. int arr[mx];
  86. struct info
  87. {
  88. int sum;
  89. int prop;
  90. }tree[mx*4];
  91.  
  92. info call(info a,info b)
  93. {
  94. info tmp;
  95. tmp.sum = min(a.sum, b.sum);
  96. tmp.prop = 0;
  97. ///merge two info
  98. return tmp;
  99. }
  100.  
  101. void init(int node,int b,int e)
  102. {
  103. if(b==e)
  104. {
  105. tree[node].sum = arr[b];
  106. tree[node].prop = 0;
  107. ///do something
  108. return;
  109. }
  110. int Left=node<<1;
  111. int Right=(node<<1)+1;
  112. int mid=(b+e)>>1;
  113. init(Left,b,mid);
  114. init(Right,mid+1,e);
  115. tree[node]=call(tree[Left],tree[Right]);
  116. }
  117.  
  118. void propagate(int node,int b,int e)
  119. {
  120. if(b==e)
  121. {
  122. tree[node].prop=0;
  123. return;
  124. }
  125. int Left=node<<1;
  126. int Right=(node<<1)+1;
  127. int mid=(b+e)>>1;
  128. ///update propagation
  129. int prop = tree[node].prop;
  130. tree[Left].prop += tree[node].prop;
  131. tree[Right].prop += tree[node].prop;
  132. tree[node].prop=0;
  133. ///update tree[left].sum
  134. // tree[Left].sum += tree[node].prop;
  135. tree[Left].sum += prop;
  136. ///update tree[right].sum
  137. // tree[Right].sum += tree[node].prop;
  138. tree[Right].sum += prop;
  139. }
  140.  
  141. int query(int node,int b,int e,int i,int j) ///range i theke j
  142. {
  143. if (i > e || j < b)return INF;
  144. if(tree[node].prop)propagate(node,b,e);
  145. if(b>=i && e<=j)
  146. {
  147. ///do something
  148. return tree[node].sum;
  149. }
  150. int Left=node<<1;
  151. int Right=(node<<1)+1;
  152. int mid=(b+e)>>1;
  153. int p1 = query(Left,b,mid,i,j);
  154. int p2 = query(Right,mid+1,e,i,j);
  155. return min(p1,p2);
  156.  
  157. }
  158.  
  159. void update(int node,int b,int e,int i,int j, int newVal)
  160. {
  161. if(tree[node].prop)propagate(node,b,e);
  162. if (i > e || j < b) return;
  163. if (b >= i && e <= j)
  164. {
  165. tree[node].sum += newVal;
  166. tree[node].prop += (newVal);
  167. ///do something
  168. return;
  169. }
  170. int Left=node<<1;
  171. int Right=(node<<1)+1;
  172. int mid=(b+e)>>1;
  173. update(Left,b,mid,i,j,newVal);
  174. update(Right,mid+1,e,i,j,newVal);
  175. tree[node]=call(tree[Left],tree[Right]);
  176. }
  177.  
  178.  
  179.  
  180. int main() {
  181. #ifdef dipta007
  182. //READ("in.txt");
  183. // WRITE("out.txt");
  184. #endif // dipta007
  185. // ios_base::sync_with_stdio(0);cin.tie(0);
  186.  
  187. int n;
  188. getI(n);
  189.  
  190. // int res= 0;
  191. // int cnt = 0;
  192. FOR(i,1,n)
  193. {
  194. getI(arr[i]);
  195. }
  196. init(1,1,n);
  197.  
  198. int cnt = 0;
  199. int i = 1;
  200. while(i <= n)
  201. {
  202. int low = i, high = n;
  203. int res = -1;
  204. while(low <= high)
  205. {
  206. int mid = (low + high) / 2;
  207. if(query(1,1,n, i, mid) <= 0)
  208. {
  209. high = mid - 1;
  210. }
  211. else
  212. {
  213. res = mid;
  214. low = mid + 1;
  215. }
  216. }
  217. if(res==-1)
  218. {
  219. i++;
  220. debug("*")
  221. continue;
  222. }
  223. cnt++;
  224. int kk = query(1,1,n, i, res);
  225. update(1,1,n,i,res,-kk);
  226. debug(i, res, kk, query(1,1,n, i, res))
  227. }
  228.  
  229.  
  230.  
  231. printf("%d\n",cnt);
  232.  
  233.  
  234. return 0;
  235. }
  236.  
Success #stdin #stdout 0.02s 19576KB
stdin
Standard input is empty
stdout
0