fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/F8AFB8
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!