oj.uz

Submission #950632

# Submission time Handle Problem Language Result Execution time Memory
950632 2024-03-20T14:10:25 Z glebustim Financial Report (JOI21_financial) C++17
5 / 100
 710 ms 90560 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

const int R = (1 << 19);
vi t(R * 2, 0);

void update(int i, int x) {
    int v = R + i;
    t[v] = x;
    v >>= 1;
    while (v > 0) {
        t[v] = max(t[v << 1], t[(v << 1) ^ 1]);
        v >>= 1;
    }
}

int get_max(int l, int r) {
    l += R;
    r += R;
    int res = 0;
    while (l < r) {
        if (l & 1) {
            res = max(res, t[l]);
            ++l;
        }
        if (!(r & 1)) {
            res = max(res, t[r]);
            --r;
        }
        l >>= 1;
        r >>= 1;
    }
    if (l == r)
        res = max(res, t[l]);
    return res;
}

vi t1(R * 2, R);

void update1(int ql, int qr, int x, int v = 1, int l = 0, int r = R) {
    if (ql >= r || l >= qr)
        return;
    if (ql <= l && r <= qr) {
        t1[v] = min(t1[v], x);
        return;
    }
    int m = (l + r) / 2;
    update1(ql, qr, x, (v << 1), l, m);
    update1(ql, qr, x, ((v << 1) ^ 1), m, r);
}

int get1(int i) {
    int v = R + i, res = R;
    while (v > 0) {
        res = min(res, t1[v]);
        v >>= 1;
    }
    return res;
}

void compress(vi &a) {
    vi b = a;
    sort(all(b));
    for (int &x: a)
        x = lower_bound(all(b), x) - b.begin();
}

int main() {
    fast;
    int n, d;
    cin >> n >> d;
    vi a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    compress(a);
    vi r(n);
    multiset<int> s;
    for (int i = n - d; i < n; ++i) {
        r[i] = n;
        s.insert(a[i]);
    }
    for (int i = n - d - 1; i >= 0; --i) {
        update1(0, *s.begin(), i);
        r[i] = min(get1(a[i]) + d, n);
        s.erase(s.find(a[i + d]));
        s.insert(a[i]);
    }
    vi b(n);
    vector<multiset<int>> c(n);
    for (int i = 0; i < n; ++i)
        c[i].insert(0);
    multiset<tuple<int, int, int>> ss;
    for (int i = 0; i < n; ++i) {
        b[i] = get_max(0, a[i] - 1) + 1;
        ss.emplace(r[i], a[i], b[i]);
        c[a[i]].insert(b[i]);
        update(a[i], *(--c[a[i]].end()));
        while (!ss.empty() && get<0>(*ss.begin()) == i) {
            c[get<1>(*ss.begin())].erase(c[get<1>(*ss.begin())].find(get<2>(*ss.begin())));
            update(get<1>(*ss.begin()), *(--c[get<1>(*ss.begin())].end()));
            ss.erase(ss.begin());
        }
    }
    int ans = 0;
    for (int i = max(n - d - 1, 0); i < n; ++i)
        ans = max(ans, b[i]);
    cout << ans << '\n';
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 3 ms 8688 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 4 ms 9052 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 3 ms 8680 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 3 ms 8536 KB Output is correct
12 Correct 3 ms 8536 KB Output is correct
13 Correct 3 ms 8540 KB Output is correct
14 Correct 3 ms 8540 KB Output is correct
15 Incorrect 3 ms 8540 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 3 ms 8688 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 4 ms 9052 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 3 ms 8680 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 3 ms 8536 KB Output is correct
12 Correct 3 ms 8536 KB Output is correct
13 Correct 3 ms 8540 KB Output is correct
14 Correct 3 ms 8540 KB Output is correct
15 Incorrect 3 ms 8540 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 3 ms 8688 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 4 ms 9052 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 3 ms 8680 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 3 ms 8536 KB Output is correct
12 Correct 3 ms 8536 KB Output is correct
13 Correct 3 ms 8540 KB Output is correct
14 Correct 3 ms 8540 KB Output is correct
15 Incorrect 3 ms 8540 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 76184 KB Output is correct
2 Incorrect 177 ms 47548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 90560 KB Output is correct
2 Correct 468 ms 90196 KB Output is correct
3 Correct 687 ms 90348 KB Output is correct
4 Correct 683 ms 90156 KB Output is correct
5 Correct 551 ms 90236 KB Output is correct
6 Correct 710 ms 90176 KB Output is correct
7 Correct 225 ms 90048 KB Output is correct
8 Correct 215 ms 90084 KB Output is correct
9 Correct 249 ms 89540 KB Output is correct
10 Correct 397 ms 89784 KB Output is correct
11 Correct 630 ms 90096 KB Output is correct
12 Correct 472 ms 90216 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 3 ms 8688 KB Output is correct
3 Correct 4 ms 8540 KB Output is correct
4 Correct 4 ms 8540 KB Output is correct
5 Correct 4 ms 9052 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 4 ms 8540 KB Output is correct
9 Correct 3 ms 8680 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 3 ms 8536 KB Output is correct
12 Correct 3 ms 8536 KB Output is correct
13 Correct 3 ms 8540 KB Output is correct
14 Correct 3 ms 8540 KB Output is correct
15 Incorrect 3 ms 8540 KB Output isn't correct
16 Halted 0 ms 0 KB -