Submission #1067402

#TimeUsernameProblemLanguageResultExecution timeMemory
1067402DucNguyen2007Money (IZhO17_money)C++14
9 / 100
1 ms2396 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pii pair<int,int> #define pll pair<ll,ll> #define fi first #define se second const int maxN=1e6+5; const ll inf=2e18; int n,a[maxN+1],pre[maxN+1]; set<ll> se; int main() { //freopen("","r",stdin); //freopen("","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; pre[i]=-1; } int pos=-1; se.insert(inf); se.insert(a[1]); for(int i=2;i<=n;i++) { if(a[i]<a[i-1]) { pos=i; break; } else se.insert(a[i]); } int cnt=1; if(pos==-1) { cout<<cnt; return 0; } cnt++; auto itr=se.upper_bound(a[pos]); int i=pos+1; ll base=(*itr); se.insert(a[pos]); while(i<=n) { while(i<=n&&a[i]>=a[i-1]&&(*se.lower_bound(a[i]))<=base) { se.insert(a[i]); i++; } //cout<<i<<" "<<(*se.upper_bound(a[i]))<<" "<<base<<'\n'; if(i<=n) { cnt++; base=(*se.upper_bound(a[i])); //cout<<i<<" "<<(*se.upper_bound(a[i]))<<'\n'; i++; } } cout<<cnt; } /*10 494573 746756 237932 746756 814455 814455 91396 494573 237932 814455*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...