fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define endl '\n'
  4.  
  5. using namespace std;
  6.  
  7. const int maxn = 2e5 + 5;
  8. const int inf = 1e18;
  9. const int MOD = 1e9 + 9;
  10. const int LIM = -1e9;
  11. const int LIM1 = -1e9 - 5;
  12. const int LIM2 = 1e9 + 5;
  13.  
  14. int add(int a, int b){
  15.     a += b;
  16.     if (a >= MOD) a -= MOD;
  17.     if (a < 0) a += MOD;
  18.     return a;
  19. }
  20.  
  21. int a[maxn], pre[maxn], dp[maxn], n;
  22.  
  23. namespace sub1{
  24.  
  25.     void solve(){
  26.         dp[0] = 1;
  27.         for (int i = 1; i <= n; i++){
  28.             for (int j = 1; j <= i; j++) if (pre[i] - pre[j-1] >= 0){
  29.                 dp[i] = add(dp[i], dp[j-1]);
  30.             }
  31.         }
  32.  
  33.         cout << dp[n];
  34.     }
  35.  
  36. }
  37.  
  38. namespace sub2{
  39.  
  40.     struct sparse_segtree{
  41.         struct node{
  42.             int sum;
  43.             node *l, *r;
  44.             node(){
  45.                 sum = 0;
  46.                 l = NULL;
  47.                 r = NULL;
  48.             }
  49.         };
  50.  
  51.         node *root;
  52.         sparse_segtree(){
  53.             root = new node();
  54.         }
  55.  
  56.         void update(node* &id, int l, int r, int pos, int val){
  57.             if (!id) id = new node();
  58.             if (l > pos or r < pos) return;
  59.             if (l == r){
  60.                 id->sum = add(id->sum, val);
  61.                 return;
  62.             }
  63.             int mid = (l + r) >> 1;
  64.             update(id->l, l, mid, pos, val);
  65.             update(id->r, mid + 1, r, pos, val);
  66.             int val1 = 0, val2 = 0;
  67.             if (id->l) val1 = id->l->sum;
  68.             if (id->r) val2 = id->r->sum;
  69.             id->sum = add(val1, val2);
  70.         }
  71.  
  72.         int get(node* id, int l, int r, int u, int v){
  73.             if (!id or l > v or r < u) return 0;
  74.             if (l >= u && r <= v) return id->sum;
  75.             int mid = (l + r) >> 1;
  76.             int get1 = get(id->l, l, mid, u, v);
  77.             int get2 = get(id->r, mid + 1, r, u, v);
  78.             return add(get1, get2);
  79.         }
  80.  
  81.         void update(int pos, int val){
  82.             update(root, LIM1, LIM2, pos, val);
  83.         }
  84.  
  85.         int get(int l, int r){
  86.             return get(root, LIM1, LIM2, l, r);
  87.         }
  88.  
  89.     };
  90.  
  91.  
  92.     void solve(){
  93.         sparse_segtree smt;
  94.         smt.update(0, 1);
  95.         for (int i = 1; i <= n; i++){
  96.             dp[i] = add(dp[i], smt.get(LIM, pre[i]));
  97.             smt.update(pre[i], dp[i]);
  98.         }
  99.         cout << dp[n];
  100.     }
  101.  
  102. }
  103.  
  104. signed main(){
  105.     ios_base::sync_with_stdio(false);
  106.     cin.tie(0); cout.tie(0);
  107.     freopen("PROTEST.INP", "r", stdin); freopen("PROTEST.OUT", "w", stdout);
  108.  
  109.     cin >> n;
  110.     for (int i = 1; i <= n; i++){
  111.         cin >> a[i];
  112.         pre[i] = pre[i-1] + a[i];
  113.     }
  114.  
  115.     if (n <= 1e4) sub1::solve(); else sub2::solve();
  116.  
  117.     return 0;
  118. }
  119. /*
  120. 4
  121. 2 3 -3 1
  122.  
  123. 20
  124. 81 90 30 -49 -23 35 54 31 66 -42 38 64 58 42 67 -31 10 -13 83 34
  125. */
  126.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TJvhNC
language:
C++14 (gcc 8.3)
created:
11 hours 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!