Submission #632573

#	Time	Username	Problem	Language	Result	Execution time	Memory
632573		KiriLL1ca	Money (IZhO17_money)	C++14	100 / 100	1008 ms	57992 KiB

money

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 3e5 + 10;

inline void solve () {
        int n; cin >> n;
        vector <int> a (n);
        for (auto &i : a) cin >> i;
        set <int> s; s.insert(1e9);
        int q = 1e9;
        int res = 0;
        for (int i = 0; i < n; ++i) {
                if (i && a[i] == a[i - 1]) continue;
                auto x = s.lower_bound(a[i]);
                if (!i || a[i - 1] > a[i] || *x != q) {
                        ++res; q = *s.upper_bound(a[i]);
                }
                s.insert(a[i]);
        }
        cout << res << endl;

}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        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