Submission #1114927

#TimeUsernameProblemLanguageResultExecution timeMemory
1114927Younis_DwaiMoney (IZhO17_money)C++14
100 / 100
814 ms61972 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> #define endl "\n" #define F first #define S second #define pb push_back //#define int long long #define in insert #define mid (l+r)/2 #define in insert using namespace std; const int N=1e6+6; int b[N],R[N],n; set<int> s; int32_t main(){ ios::sync_with_stdio(false);cin.tie(nullptr); cin>>n; for(int i=1;i<=n;i++) cin>>b[i]; R[n]=n; for(int i=n-1;i>=1;i--){ if(b[i]<=b[i+1]) R[i]=R[i+1]; else R[i]=i; } int ret=1,id=R[1]; s.in(1e9+9); for(int i=1;i<=id;i++) s.in(b[i]); if(id!=n) ++ret; ++id; while(id<n){ //cout<<" # "<<id<<endl; int nxt=*(s.upper_bound(b[id])); bool done=0; for(int j=id;j<=R[id];j++){ if(b[j]<=nxt){ s.in(b[j]); } else{ ++ret; id=j; done=1; break; } } if(!done){ id=R[id]+1; if(id<=n) ++ret; } } cout<<ret<<endl; 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...