#include <bits/stdc++.h> using namespace std; #define mk make_pair #define fst first #define sz(x) x.size() #define snd second #define pb push_back #define VAR(v) #v << " = " << v << " " #define debug if(0) #define M_PI 3.14159265358979323846 typedef complex<long double> C; typedef long long ll; typedef pair<int, int> ii; typedef vector<ll> Matrix; const int maxn = (int)11e5 + 9; const int INF = (int)1e9 + 7; int mod = (int)1e9 + 7; ll tab[maxn], pref[maxn]; int T[maxn]; int n, N = 1; void add(int pos, int val){ pos += N; T[pos] = val; pos /= 2; while(pos){ T[pos] = min(T[2*pos], T[2*pos+1]); pos /= 2; } } int query(int l, int r){ l += N, r += N; int ret = INF; while(l < r) { //debug cout << VAR(l) << VAR(r) << endl; if(l&1) ret = min(ret, T[l++]); if(!(r&1)) ret = min(ret, T[r--]); l /= 2, r /= 2; } if(l == r) ret = min(ret, T[l]); return ret; } ll toBin[maxn]; int PosInTree[maxn]; void Prep(){ while(N <= n) N *= 2; for(int i = 0; i <= 2*N; i++) T[i] = INF; vector<pair<ll, int>> vec; for(int i = 0; i <= n; i++) vec.pb(mk(pref[i], i)); sort(vec.begin(), vec.end()); for(int i = 0; i < vec.size(); i++){ pair<ll, int> p = vec[i]; PosInTree[p.snd] = i; toBin[i] = p.fst; } debug{ cout<<VAR(n) << VAR(N) << endl; for(int i = 0; i <= n + 1; i++){ cout<<VAR(i)<<endl; cout << VAR(pref[i]) << VAR(tab[i]) << VAR(PosInTree[i])<<endl; } for(int i = 0; i <= n; i++) cout<<i<<"\t"; cout<<endl; for(int i = 0; i <= n; i++) cout<<toBin[i]<<"\t"; cout<<endl; } } int get_range(ll x){ int low = 0, high = n + 2; while(high - low > 1){ int mid = (low + high)/2; //debug cout << VAR(mid) << VAR(x) << VAR(toBin[mid])<<endl; if(x >= toBin[mid]) low = mid; else high = mid; } return low; } void ComputeDp(){ add(PosInTree[0], -1); for(int k = 1; k <= n; k++){ int range = get_range(pref[k]); ll val = query(0, range); debug cout << VAR(k) << VAR(pref[k]) << VAR(PosInTree[k]) << VAR(range) << VAR(val) <<endl; add(PosInTree[k], val - 1); debug{ for(int i = 0; i <= n; i++) cout<<i<<"\t"; cout<<endl; for(int i = 0; i <= n; i++) cout<<query(i, i)<<"\t"; cout<<endl; } } } int main(int argc, char* argv[]) { ios::sync_with_stdio(false); debug; else cin.tie(NULL), cout.tie(NULL); cin>>n; for(int i = 1; i <= n; i++){ cin>>tab[i]; pref[i] = pref[i-1] + tab[i]; } debug cout << "OK"<<endl; Prep(); ComputeDp(); int res = query(PosInTree[n], PosInTree[n]) + n + 1; if(res <= n) cout<<res<<"\n"; else cout<<-1<<"\n"; debug{ for(int i = 0; i <= n; i++) cout<<query(PosInTree[i], PosInTree[i]) + i + 1<<" "; cout<<endl; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | #include <bits/stdc++.h> using namespace std; #define mk make_pair #define fst first #define sz(x) x.size() #define snd second #define pb push_back #define VAR(v) #v << " = " << v << " " #define debug if(0) #define M_PI 3.14159265358979323846 typedef complex<long double> C; typedef long long ll; typedef pair<int, int> ii; typedef vector<ll> Matrix; const int maxn = (int)11e5 + 9; const int INF = (int)1e9 + 7; int mod = (int)1e9 + 7; ll tab[maxn], pref[maxn]; int T[maxn]; int n, N = 1; void add(int pos, int val){ pos += N; T[pos] = val; pos /= 2; while(pos){ T[pos] = min(T[2*pos], T[2*pos+1]); pos /= 2; } } int query(int l, int r){ l += N, r += N; int ret = INF; while(l < r) { //debug cout << VAR(l) << VAR(r) << endl; if(l&1) ret = min(ret, T[l++]); if(!(r&1)) ret = min(ret, T[r--]); l /= 2, r /= 2; } if(l == r) ret = min(ret, T[l]); return ret; } ll toBin[maxn]; int PosInTree[maxn]; void Prep(){ while(N <= n) N *= 2; for(int i = 0; i <= 2*N; i++) T[i] = INF; vector<pair<ll, int>> vec; for(int i = 0; i <= n; i++) vec.pb(mk(pref[i], i)); sort(vec.begin(), vec.end()); for(int i = 0; i < vec.size(); i++){ pair<ll, int> p = vec[i]; PosInTree[p.snd] = i; toBin[i] = p.fst; } debug{ cout<<VAR(n) << VAR(N) << endl; for(int i = 0; i <= n + 1; i++){ cout<<VAR(i)<<endl; cout << VAR(pref[i]) << VAR(tab[i]) << VAR(PosInTree[i])<<endl; } for(int i = 0; i <= n; i++) cout<<i<<"\t"; cout<<endl; for(int i = 0; i <= n; i++) cout<<toBin[i]<<"\t"; cout<<endl; } } int get_range(ll x){ int low = 0, high = n + 2; while(high - low > 1){ int mid = (low + high)/2; //debug cout << VAR(mid) << VAR(x) << VAR(toBin[mid])<<endl; if(x >= toBin[mid]) low = mid; else high = mid; } return low; } void ComputeDp(){ add(PosInTree[0], -1); for(int k = 1; k <= n; k++){ int range = get_range(pref[k]); ll val = query(0, range); debug cout << VAR(k) << VAR(pref[k]) << VAR(PosInTree[k]) << VAR(range) << VAR(val) <<endl; add(PosInTree[k], val - 1); debug{ for(int i = 0; i <= n; i++) cout<<i<<"\t"; cout<<endl; for(int i = 0; i <= n; i++) cout<<query(i, i)<<"\t"; cout<<endl; } } } int main(int argc, char* argv[]) { ios::sync_with_stdio(false); debug; else cin.tie(NULL), cout.tie(NULL); cin>>n; for(int i = 1; i <= n; i++){ cin>>tab[i]; pref[i] = pref[i-1] + tab[i]; } debug cout << "OK"<<endl; Prep(); ComputeDp(); int res = query(PosInTree[n], PosInTree[n]) + n + 1; if(res <= n) cout<<res<<"\n"; else cout<<-1<<"\n"; debug{ for(int i = 0; i <= n; i++) cout<<query(PosInTree[i], PosInTree[i]) + i + 1<<" "; cout<<endl; } return 0; } |