제출 #1159060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159060		MisterReaper	Money (IZhO17_money)	C++20	0 / 100	0 ms	328 KiB

money

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

struct Fenwick {
    int n;
    std::vector<int> tree;
    Fenwick(int n_) : n(n_), tree(n + 1) {}
    void modify(int p, int x) {
        for (p += 1; p <= n; p += p & -p) {
            tree[p] += x;
        }
    }
    int query(int p) {
        int res = 0;
        for (p += 1; p; p -= p & -p) {
            res += tree[p];
        }
        return res;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    std::vector<int> vec(A.begin(), A.end());
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    for (int i = 0; i < N; ++i) {
        A[i] = std::lower_bound(vec.begin(), vec.end(), A[i]) - vec.begin();
    }

    Fenwick fen(N);
    int ans = 0;
    for (int i = 0, j = 0; i < N; i = ++j) {
        int mn = A[i], mx = A[i];
        while (j + 1 < N && A[j] <= A[j + 1]) {
            j++;
            mn = std::min(mn, A[j]);
            mx = std::max(mx, A[j]);
            if (fen.query(mn + 1, mx - 1)) {
                --j;
                break;
            }
        }
        for (int k = i; k <= j; ++k) {
            fen.modify(A[k], +1);
        }
        ans++;
    }

    std::cout << ans << '\n';

    return 0;
}

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