제출 #888268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888268		drAKu	Money (IZhO17_money)	C++17	0 / 100	10 ms	29020 KiB

money

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e6 + 1;
int a[N], ans[N];
vector<int> pos[N];
int connected[N];
const int G = (1 << 20);
int t[2 * G];
void change(int ql, int qr) {
    ql += G;
    qr += G;
    for (; ql <= qr; ql >>= 1, qr >>= 1) {
        if (ql & 1) t[ql++] = 1;
        if (~qr & 1) t[qr--] = 1;
    }
}
int cool(int ql) {
    ql += G;
    int good = 1;
    for (; ql; ql >>= 1) good &= !t[ql];
    return good;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pos[a[i]].push_back(i);
    }
    for (int i = 1; i < N; i++) {
        for (auto id : pos[i]) {
            if (id == 0 || a[id-1] > i || !cool(a[id-1])) continue;
            ans[id] = 1;
            if (a[id-1] <= i-1) change(a[id-1], i-1);
        }
    }
    cout << n - accumulate(ans, ans + N, 0) << "\n";
}

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