fork download
copy 
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC target("avx,avx2,fma")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define MOD 1000000007
  9. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)   
  10. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define ii pair<int,int>
  13. #define iii pair<ll,pair<int,int>>
  14. //const int MOD = 998244853;
  15. const int MAXN = 5e5 + 7;
  16. int a[MAXN],f[MAXN];
  17. ll diff[MAXN],seg[MAXN * 4];
  18. void update(int id,int l,int r,int pos,ll v){
  19.     if (l > pos || pos > r)return ;
  20.     if (l == r){
  21.         seg[id] = v;
  22.         return ;
  23.     }
  24.     int mid = (l + r) / 2;
  25.     update(id * 2,l,mid,pos,v);
  26.     update(id * 2 + 1,mid + 1,r,pos,v);
  27.     seg[id] = min(seg[id * 2],seg[id * 2 + 1]);
  28. }
  29. ll Find(int id,int l,int r,int u,ll k){
  30.     if (r < u || seg[id] > k)return -1;
  31.     if (l == r)return l;
  32.     int ans = -1;
  33.     int mid = (l + r) / 2;
  34.     if (seg[id * 2] <= k)ans = Find(id * 2,l,mid,u,k);
  35.     if (ans == -1)ans = Find(id * 2 + 1,mid + 1,r,u,k);
  36.     return ans;
  37. }
  38. int main(){
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(0); cout.tie(0);
  41.     //freopen("GRAPH01.inp","r",stdin);
  42.     //freopen("GRAPH01.out","w",stdout);
  43.     int n;cin >> n;
  44.     FOR(i,1,n)cin >> a[i];
  45.     FOD(i,1,n){
  46.         diff[i] = diff[i + 1] + a[i];
  47.         int id = Find(1,1,n + 1,i + 1,diff[i]);
  48.         update(1,1,n + 1,i,2 * diff[i] - diff[id]);
  49.         f[i] = f[id] + 1;
  50.     }
  51.     cout << f[1];
  52.     return 0^0;
  53. }
  54. /*
  55. diff[i] >= last[j] + diff[j];
  56. last[j] = diff[j] - diff[k];
  57. => diff[i] >= 2 * diff[j] - diff[k];
  58. */
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5455
https://ideone.com/upG0Vv
language:
C++ (gcc 8.3)
created:
5 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!