제출 #892402

#제출 시각아이디문제언어결과실행 시간메모리
892402LeVanThucBigger segments (IZhO19_segments)C++17
0 / 100
6 ms25432 KiB
#include<bits/stdc++.h> using namespace std; #define ll int #define fi first #define se second #define p(x,y) pair<ll,ll>(x,y) #define BIT(i,x) ((x>>i)&1) #define MASK(x) (1<<x) #define ld long double #define __builtin_popcount __builtin_popcountll #define pll pair<ll,ll> #define kt cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n" template<class T1,class T2> bool maximize(T1 &x,T2 y) { if(x<y) { x=y; return 1; } return 0; } template<class T1,class T2> bool minimize(T1 &x,T2 y) { if(y<x) { x=y; return 1; } return 0; } const ll M=1e9+7; template <class T1,class T2> void add(T1 &x,T2 y) { x+=y; if(x>=M) x-=M; } template <class T1,class T2> void sub(T1 &x, T2 y) { x-=y; if(x<0) x+=M; } void online() { std::ios_base::sync_with_stdio(0); cin.tie(0); #ifdef thuc freopen("input.inp","r",stdin); freopen("output.out","w",stdout); #else #endif // thuc } const ll N=5e5+10,S=400; ll n,a[N]; vector<pll> f1[N],f2[N]; void them(ll i,ll l,ll vl) { l++; if(f1[i].back().se==vl) { f1[i].emplace_back(l,vl); return; } if(f2[i].size()&&f2[i].back().se==vl) { f2[i].emplace_back(l,vl); return; } else if(f2[i].empty()||f2[i].back().se<vl) { f2[i].clear(); f2[i].emplace_back(l,vl); if(f1[i].back().se<f2[i].back().se) f1[i].swap(f2[i]); return; } } int main() { online(); cin>>n; for(int i=1; i<=n; i++) { cin>>a[i]; a[i]+=a[i-1]; } a[n+1]=a[n]; ll ans=1; for(int i=1; i<=n; i++) { f1[i].emplace_back(1,1); } for(int i=1; i<=n; i++) { sort(f1[i].begin(),f1[i].end()); if(f1[i].size()) { ll l=f1[i].back().fi,vl=f1[i].back().se; ll sum=a[i]-a[l-1]; ll r=i; ll d=n/2; while(d) { while(r+d<=n&&a[r+d]-a[i]<sum) r+=d; d/=2; } r++; if(a[r]-a[i]>=sum) { vl++; them(r,i,vl); } } if(f2[i].size()) { sort(f2[i].begin(),f2[i].end()); ll l=f2[i].back().fi,vl=f2[i].back().se; ll sum=a[i]-a[l-1]; ll r=i; ll d=n/2; while(d) { while(r+d<=n&&a[r+d]-a[i]<sum) r+=d; d/=2; } r++; if(a[r]-a[i]>=sum) { vl++; them(r,i,vl); } } } maximize(ans,f1[n].back().se); cout<<ans; kt; }
#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...