Submission #1128274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128274		the_ZHER	Money (IZhO17_money)	C++20	100 / 100	714 ms	55232 KiB

money

#include <bits/stdc++.h>
#define int long long
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = (500*500)+1;
const int inf = 1e9;
const int mod=1e9+7;
struct edge{
    int x,y,c;
};
vector<int>v;
signed main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
    boost 
    int n;
    cin>>n;
    v.push_back(0);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        v.push_back(x);
    }
    multiset<int>st;
    int ans=0;
    for(int i=1;i<=n;){
        ans++;
        int r=i;
        auto j=st.upper_bound(v[i]);
        while(r<n&&v[r]<=v[r+1]&&(st.lower_bound(v[r+1])==j||st.upper_bound(v[r+1])==j)){
            r++;
        }
        for(int l=i;l<=r;l++){
            st.insert(v[l]);
        }
        i=r+1;
    }
    cout<<ans;
}

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