oj.uz

Submission #888268

# Submission time Handle Problem Language Result Execution time Memory
888268 2023-12-16T18:23:11 Z drAKu Money (IZhO17_money) C++17
0 / 100
 10 ms 29020 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 29016 KB Output is correct
2 Correct 10 ms 29016 KB Output is correct
3 Correct 8 ms 29020 KB Output is correct
4 Incorrect 9 ms 29020 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 29016 KB Output is correct
2 Correct 10 ms 29016 KB Output is correct
3 Correct 8 ms 29020 KB Output is correct
4 Incorrect 9 ms 29020 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 29016 KB Output is correct
2 Correct 10 ms 29016 KB Output is correct
3 Correct 8 ms 29020 KB Output is correct
4 Incorrect 9 ms 29020 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 29016 KB Output is correct
2 Correct 10 ms 29016 KB Output is correct
3 Correct 8 ms 29020 KB Output is correct
4 Incorrect 9 ms 29020 KB Output isn't correct
5 Halted 0 ms 0 KB -