Submission #336393

#TimeUsernameProblemLanguageResultExecution timeMemory
336393talant117408Bigger segments (IZhO19_segments)C++17
13 / 100
1 ms364 KiB
/* Code written by Talant I.D. */ #include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //using namespace __gnu_pbds; using namespace std; //typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define precision(n) fixed << setprecision(n) #define pb push_back #define ub upper_bound #define lb lower_bound #define mp make_pair #define eps (double)1e-9 #define PI 2*acos(0.0) #define endl "\n" #define sz(v) int((v).size()) #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define OK cout << "OK" << endl; inline bool isvowel(char ch){ ch = tolower(ch); return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'); } inline bool isprime(int n){ if(n < 2 || (n%2 == 0 && n != 2)) return false; for(int i = 3; i*i <= n; i++) if(n%i == 0) return false; return true; } class Union{ private: vector <int> saizu, link; public: Union(int n){ saizu.assign(n, 1); link.resize(n); iota(all(link), 0); } int find(int n){ if(link[n] == n) return n; return link[n] = find(link[n]); } int same(int a, int b){ return find(a) == find(b); } void unite(int a, int b){ if(same(a, b)) return; a = find(a); b = find(b); if(saizu[a] < saizu[b]) swap(a, b); saizu[a] += saizu[b]; link[b] = a; } int getsize(int a){ return saizu[find(a)]; } }; const int mod = 1e9+7; ll mode(ll a){ a %= mod; if(a < 0) a += mod; return a; } ll subt(ll a, ll b){ return mode(mode(a)-mode(b)); } ll add(ll a, ll b){ return mode(mode(a)+mode(b)); } ll mult(ll a, ll b){ return mode(mode(a)*mode(b)); } ll binpow(ll a, ll b){ ll res = 1; while(b){ if(b&1) res = mult(res, a); a = mult(a, a); b >>= 1; } return res; } /* struct point{ double x, y; bool operator < (point other){ if(x == other.x) return y < other.y; return x < other.x; } }; struct line{ double a, b, c; }; double dot(point a, point b, point c){ a.x -= c.x; b.x -= c.x; a.y -= c.y; b.y -= c.y; return a.x*b.y-b.x*a.y; } double det(double a, double b, double c, double d){ return a*d-b*c; } bool intersect(line x, line y){ double zn = det(x.a, x.b, y.a, y.b); if(abs(zn) < eps) return false; return true; } vector <point> hull; void convex_hull(vector <point> v){ int i; for(i = 0; i < sz(v); i++){ hull.pb(v[i]); while(sz(hull) > 2){ auto it = dot(hull[sz(hull)-2], hull.back(), hull[sz(hull)-3]); if(it > 0){ auto to = hull.back(); hull.pop_back(); hull.pop_back(); hull.pb(to); } else break; } } for(i = sz(v)-2; i >= 0; i--){ hull.pb(v[i]); while(sz(hull) > 2){ auto it = dot(hull[sz(hull)-2], hull.back(), hull[sz(hull)-3]); if(it > 0){ auto to = hull.back(); hull.pop_back(); hull.pop_back(); hull.pb(to); } else break; } } } */ const int N = 5e5+7; ll dp[N], pref[N]; int main(){ do_not_disturb /*int n; cin >> n; vector <point> v(n); for(auto &to : v) cin >> to.x >> to.y; sort(all(v)); convex_hull(v); int left = n-sz(hull); int ptmp = 3, etmp = 3; while(ptmp < n){ ptmp++; etmp += 2; } */ int n, i; cin >> n; for(i = 1; i <= n; i++){ cin >> pref[i]; pref[i] += pref[i-1]; } int ind = 0; priority_queue <pair <ll, int>> K; K.push(mp(0, 0)); for(i = 1; i <= n; i++){ while(sz(K) && -K.top().first <= pref[i]-pref[K.top().second]){ if(dp[ind] < dp[K.top().second] || (dp[ind] == dp[K.top().second] && ind < K.top().second)) ind = K.top().second; K.pop(); } dp[i] = dp[ind] + 1; K.push(mp(pref[ind]-pref[i], i)); } cout << dp[n]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...