oj.uz

Submission #1114926

# Submission time Handle Problem Language Result Execution time Memory
1114926 2024-11-19T19:36:06 Z Younis_Dwai Money (IZhO17_money) C++14
0 / 100
 1 ms 2384 KB 
#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;
          if(b[id]>*prev(s.end())){
             id=R[id]+1;
             ret++;
          }
          else if(b[id]<*s.begin()){
               int nxt=*(++s.begin());
               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;
               }
          }
          else{
               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;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Incorrect 1 ms 2384 KB Output isn't correct
4 Halted 0 ms 0 KB -