Submission #1307432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307432		ballbreaker	Money (IZhO17_money)	C++20	100 / 100	835 ms	219744 KiB

money

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,sse,sse2,sse3,sse4,tune=native")
#define endl "\n"
using namespace std;
main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int a[n + 1] = {};
    int sp[20][n + 1];
    int spp[20][n + 1];
    int logs[n + 1];
    logs[0] = -1;
    int pref[n + 1] = {};
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        logs[i] = logs[i / 2] + 1;
        sp[0][i] = a[i];
        spp[0][i] = a[i];
        pref[i] = pref[i - 1] + (a[i - 1] > a[i]);
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            sp[j][i] = min(sp[j - 1][i], sp[j - 1][i + (1 << (j - 1))]);
            spp[j][i] = max(spp[j - 1][i], spp[j - 1][i + (1 << (j - 1))]);
        }
    }
    int dp[n + 1] = {};
    fill(dp + 1, dp + n + 1, INT_MAX);
    set<int>s;
    for (int i = 0; i < n; i++) {
        dp[i + 1] = min(dp[i + 1], dp[i] + 1);
        if (i >= 1) {
            s.insert(a[i]);
        }
        int l = i + 1, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            int u = logs[mid - i];
            int mn = min(sp[u][i + 1], sp[u][mid - (1 << u) + 1]);
            int mx = max(spp[u][i + 1], spp[u][mid - (1 << u) + 1]);
            if ((pref[mid] - pref[i + 1]) != 0 || (!s.empty() && *s.rbegin() > mn && *s.upper_bound(mn) < mx)) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        dp[l] = min(dp[l], dp[i] + 1);
        // cout << i + 1 << ' ' << l << endl;
    }
    cout << dp[n];
}

Compilation message (stderr)

money.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main() {
      | ^~~~

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