Submission #1067422

#TimeUsernameProblemLanguageResultExecution timeMemory
1067422vjudge1Money (IZhO17_money)C++17
100 / 100
679 ms58960 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<<" "<<cnt<<" "<<base<<'\n'; if(i<=n) { cnt++; base=(*se.upper_bound(a[i])); se.insert(a[i]); //cout<<i<<" "<<(*se.upper_bound(a[i]))<<'\n'; i++; } } cout<<cnt; } /*20 324662 468027 324662 324662 468027 324662 468027 324662 324662 468027 963343 944165 165047 127072 405908 918630 854332 571550 909067 448963*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...