Submission #1232572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232572		Bahamin	Money (IZhO17_money)	C++20	100 / 100	611 ms	118272 KiB

money

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e6 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

int mi[MAX_N];

void solve() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    set<int> al;
    bool ok[n];
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] > a[i + 1]) ok[i] = false;
        else 
        {
            auto x = al.upper_bound(a[i]);
            if (x != al.end() && (*x) < a[i + 1]) ok[i] = false;
            else ok[i] = true;
        }
    }
    int mi[n];
    al.clear();
    for (int i = 0; i < n; i++) 
    {
        auto x = al.upper_bound(a[i]);
        if (x == al.end()) mi[i] = 1e6;
        else mi[i] = *x;
        al.insert(a[i]);
        // cout << i << " " << mi[i] << endl;
    }
    // cout << "oh" << endl;
    vector<int> now;
    int r[n];
    vector<int> e[n];
    for (int i = n - 1; i >= 0; i--)
    {
        if (i < n - 1 && !ok[i]) now.clear();
        now.push_back(i);
        int r1 = now.size() - 1;
        int l1 = -1;
        while (r1 - l1 > 1)
        {
            int mid = (l1 + r1) >> 1;
            if (a[now[mid]] <= mi[i]) r1 = mid;
            else l1 = mid;
        }
        r[i] = now[r1];
        e[r[i]].push_back(i);
        // cout << i << " " << r[i] << endl;
    }
    // cout << "oh1" << endl;
    int l[n];
    al.clear();
    for (int i = 0; i < n; i++)
    {
        if (i > 0 && !ok[i - 1]) al.clear();
        al.insert(i);
        l[i] = *al.begin();
        for (int x : e[i]) if (al.find(x) != al.end()) al.erase(x);
        // cout << i << " " << l[i] << endl;
    }
    int ind = n - 1;
    int ans = 0;
    while (ind > -1)
    {
        ind = l[ind] - 1;
        ans++;
    }
    cout << ans << "\n";
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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