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