fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define F first
  4. #define S second
  5. typedef long long ll;
  6. void qread(int &x){
  7. 	int neg=1;x=0;
  8. 	register char c=getchar();
  9. 	while(c<'0'||c>'9'){if(c=='-')neg=-1;c=getchar();}
  10. 	while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
  11. 	x*=neg;
  12. }
  13. void Wl(int x)
  14. {
  15.     printf("%d\n",x);
  16. }
  17. ll qs[100005];
  18. map<ll,int> mp;
  19. int dp[100005];
  20. struct Node
  21. {
  22.     int val;
  23.     Node *l,*r;
  24.     void compute()
  25.     {
  26.         val = max(l->val,r->val);
  27.     }
  28.     Node(Node *l,Node *r):l(l),r(r){
  29.         compute();
  30.     }
  31.     Node(int val):l(nullptr),r(nullptr),val(val){}
  32. };
  33. Node *build(int l,int r)
  34. {
  35.     if(l==r)return new Node(INT_MIN);
  36.     int md=(l+r)/2;
  37.     return new Node(build(l,md),build(md+1,r));
  38. }
  39. int query(Node *now,int l,int r,int x,int y)
  40. {
  41.     if(y<l || x>r)return INT_MIN;
  42.     if(x<=l && r<=y)return now->val;
  43.     int md=(l+r)/2;
  44.     return max(query(now->l,l,md,x,y),query(now->r,md+1,r,x,y));
  45. }
  46. void update(Node *now,int l,int r,int pos,int val)
  47. {
  48.     if(l==r)
  49.     {
  50.         now->val = val;
  51.         return;
  52.     }
  53.     int md=(l+r)/2;
  54.     if(pos<=md)update(now->l,l,md,pos,val);
  55.     else update(now->r,md+1,r,pos,val);
  56.     now->compute();
  57. }
  58. int main()
  59. {
  60.     int n, tmp;
  61. 	qread(n);
  62.     for(int i=1;i<=n;i++)
  63.     {
  64.         qread(tmp);
  65.         qs[i]=qs[i-1]+tmp;
  66.         mp[qs[i]];
  67.     }
  68.     int cnt=0;
  69.     auto it=mp.begin();
  70.     while(it!=mp.end())
  71.     {
  72.         mp[(*it).F]=++cnt;
  73.         it++;
  74.     }
  75.     Node *root=build(1,n);
  76.     for(int i=1;i<=n;i++)
  77.     {
  78.         int u=query(root,1,n,1,mp[qs[i]]-1);
  79.         if(u==INT_MIN)
  80.         {
  81.             if(qs[i]>0)dp[i]=1;
  82.             else if(qs[i]==0)dp[i]=0;
  83.             else dp[i]=INT_MIN;
  84.         }
  85.         else dp[i]=u+1;
  86.         update(root,1,n,mp[qs[i]],dp[i]);
  87.     }
  88.     Wl(dp[n]);
  89.     #ifdef TIME
  90.     	printf("Running Time = %d ms\n",int(clock()*1000.0/CLOCKS_PER_SEC));
  91.     #endif
  92. }
  93. /*
  94.  
  95. */
Success #stdin #stdout 0s 16408KB
comments (?)
stdin 
5
1 2 3 -4 5
stdout 
4
https://ideone.com/2BMs6Z
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!