Submission #170512

#	Time	Username	Problem	Language	Result	Execution time	Memory
170512		dxz05	Money (IZhO17_money)	C++14	100 / 100	1491 ms	76180 KiB

money

#include <bits/stdc++.h>

using namespace std;
#define sqr(x) ((x)*(x))
#define cube(x) ((x)*(x)*(x))
#define GCD(a, b) __gcd(a, b)
#define LCM(a, b) ((a)*(b)/GCD(a,b))
#define MP make_pair
#define n1 first
#define n2 second
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define SI set<int>
#define SL set<ll>
#define MS multiset
#define MSI multiset<int>
#define MSLL multiset<ll>
#define PB push_back
#define PF push_front
#define VI vector<int>
#define VPI vector<pair<int,int>>
#define VLL vector<ll>
#define SZ(x) ((int)x.size())

typedef long long ll;

typedef unsigned long long ull;
typedef long double ld;
typedef double db;
const int INF = 1e9;
const int MOD = 1000000007;
const int N = 1001000;
const int M = 2511;

int a[N];
VI v[N];

void solve() {
    int n;
    cin >> n;


    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    set<int> s;
    s.insert(-1);
    s.insert(1e7);
    int ans = 0;
    int r = 1e7;
    for (int i = 1; i <= n; i++) {

        if (a[i] >= a[i - 1] && a[i] <= r) {
            s.insert(a[i]);
        } else {
          //  cout << " | ";
            s.insert(a[i]);
            r = *++s.find(a[i]);
            ans++;
        }
        //cout << a[i] << ' ';
    }
    cout << ans + 1<< endl;

}

int main() {
    ios_base::sync_with_stdio(false);
#ifdef dxz05
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif

    int T = 1;
    //cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

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