Submission #1270959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270959		LucasLe	Money (IZhO17_money)	C++20	100 / 100	759 ms	70888 KiB

money

#include <bits/stdc++.h>
 
#define fi first
#define se second
#define ld long double
#define pii std::pair<int, int>
#define piii std::pair<pii, pii>

#define rep(i,a) for (int i = 0; i < a; ++i)
#define per(i,a) for (int i = a - 1; i >= 0; --i)

const int maxn = 1e6 + 5;
const int INF = 1e9;

int N;
int a[maxn + 5];
int dp[maxn + 5];

struct segment_tree {
    int info[4 * maxn + 5];

    void modify(int id, int l, int r, int pos, int x) {
        if (l == r) {
            info[id] = x;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            modify(id << 1, l, mid, pos, x);
        else
            modify(id << 1 | 1, mid + 1, r, pos, x);
        info[id] = std::min(info[id << 1], info[id << 1 | 1]);
    }

    int query(int id, int l, int r, int lb, int rb) {
        if (lb <= l && r <= rb) {
            return info[id];
        }
        int mid = (l + r) >> 1;
        int a = INF, b = INF;
        if (lb <= mid)
            a = query(id << 1, l, mid, lb, rb);
        if (rb > mid)
            b = query(id << 1 | 1, mid + 1, r, lb, rb);
        return std::min(a, b);
    }

    void modify(int pos, int x) {
        modify(1, 1, N, pos, x);
    }
    int query(int l, int r) {
        return query(1, 1, N, l, r);
    }
} ST;

void solve() {
    std::cin >> N;
    for (int i = 1; i <= N; ++i)
        std::cin >> a[i];

    for (int i = 1; i <= 4 * N; ++i) ST.info[i] = INF;
    ST.modify(1, 0);

    int pos = 1;
    std::set<int> s;
    std::vector<int> vec;

    for (int i = 1; i <= N; ++i) {
        if (a[i] < a[i - 1]) {
            for (int j = pos; j < i; ++j)
                s.insert(a[j]);
            pos = i;
            vec.clear();
        }

        vec.push_back(a[i]);

        // [pos...i]

        int val = 0;
        auto ptr = s.lower_bound(a[i]);
        if (ptr != s.begin()) {
            ptr--;
            val = *ptr;
        }
        
        int vt = lower_bound(vec.begin(), vec.end(), val) - vec.begin();
        dp[i] = ST.query(pos + vt, i) + 1;

        if (dp[i] != INF)
            ST.modify(i + 1, dp[i]);
    }

    std::cout << dp[N] << '\n';
}

int main() {
    // std::freopen("input.txt", "r", stdin);
    // std::freopen("palin.inp", "r", stdin);
    // std::freopen("sushi.out", "w", stdout);
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);

    int T = 1; 
    // std::cin >> T;
    while (T--)
        solve();

}

// 14 / 2 (87.5% Rate)

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