Submission #910597

#TimeUsernameProblemLanguageResultExecution timeMemory
910597vjudge1Money (IZhO17_money)C++17
100 / 100
568 ms22324 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization("unroll-loops") #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") #include <bits/stdc++.h> #include <iomanip> #define ll long long #define pb push_back #define mp make_pair #define ff first #define ss second #define str string #define pii pair<int,int> #define sz(x) x.size() #define all(x) x.begin(), x.end() #define vi vector<int> #define mii map<int,int> #define mll map<ll,ll> #define yes cout<<"YES\n"; #define no cout<<"NO\n"; #define yess cout<<"Yes\n"; #define noo cout<<"No\n"; using namespace std; int t[3000001],sum=0; void get(int v,int tl,int tr,int l,int r){ if(tl>=l && tr<=r){ sum+=t[v]; return; } if(tl>r || tr<l){ return; } int tm=(tl+tr)>>1; get(v+v,tl,tm,l,r); get(v+v+1,tm+1,tr,l,r); } void upd(int v,int tl,int tr,int l,int r){ if(tl>=l && tr<=r){ t[v]=1; return; } if(tl>r || tr<l){ return; } int tm=(tl+tr)>>1; upd(v+v,tl,tm,l,r); upd(v+v+1,tm+1,tr,l,r); t[v]=t[v+v]+t[v+v+1]; } int pp[1000001]; void solve(){ int n; cin>>n; int a[n+3]; for(int i=1;i<=n;i++){ cin>>a[i]; } int ans=0; a[0]=-1; for(int i=1;i<=n;i++){ int o=i; for(int j=i+1;j<=n;j++){ if(a[j]<a[j-1]){ break; } sum=0; get(1,1,1000000,a[i],a[j]); if(sum-pp[a[i]]-pp[a[j]]>0){ o=j-1; break; } else{ o=j; } } for(int j=i;j<=o;j++){ upd(1,1,1000000,a[j],a[j]); pp[a[j]]=1; } ans++; i=o; } cout<<ans; } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); //srand( time(0)); //rand() //freopen("sum.in", "r", stdin); //freopen("sum.out", "w", stdout); int tests=1; //cin>>tests; for(int i=1;i<=tests;i++){ //cout<<"TEST CASE : "<<i<<"\n"; solve(); } }

Compilation message (stderr)

money.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("unroll-loops")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...