Submission #1128257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128257		syanvu	Money (IZhO17_money)	C++20	100 / 100	912 ms	55228 KiB

money

#include <bits/stdc++.h>

#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define int long long
#define all(x) x.begin(),x.end()
#define F first
#define S second

using namespace std;


const int LG = 40,N=1e6+1,P1=31,P2=37, MOD = 1e9+7;
const long double eps = 1e-9;
int inf = 1e9;
int T;

//struct mint
//{
//public:
//    int v;
//    mint(int _v=0):v(_v){}
//    explicit operator int() const {return v;}
//    mint& operator += (const mint& o) {if((v+=o.v)>=MOD) v-=MOD; return *this;}
//    mint& operator -= (const mint& o) {if((v-=o.v)<0) v+=MOD; return *this;}
//    mint& operator *= (const mint& o) {v=(int)v*o.v%MOD; return *this;}
//    friend mint operator + (mint a, const mint& b) {return a+=b;}
//    friend mint operator - (mint a, const mint& b) {return a-=b;}
//    friend mint operator * (mint a, const mint& b) {return a*=b;}
//    friend mint pow(mint b, int p)
//    { mint f(1); for(;p;p>>=1, b*=b) if(p&1) f*=b; return f; }
//};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int myRand(int B) {
    return (int) rng()%B;
}

void solve(){
    int n;
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=0;
    set<int> st;
    for(int i=1;i<=n;i++){
        int j=i+1;
        auto id=st.upper_bound(a[i]);
        while(j<=n){
            if(a[j-1]>a[j]){
                break;
            }
            auto it=st.lower_bound(a[j]);
            auto itt=st.upper_bound(a[j]);
            if(id!=it && id!=itt){
                break;
            }
            j++;
        }
        j--;
        ans++;
        for(int k=i;k<=j;k++){
            st.insert(a[k]);
        }
        i=j;
    }
    cout<<ans;
}

signed main() {
    SS
    int t=1;
    if(T) {
        cin >> t;
    }
    while(t--) {
        solve();
    }
}
/*
 * 2 4 5 1 3
 */

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55