oj.uz

Submission #950643

# Submission time Handle Problem Language Result Execution time Memory
950643 2024-03-20T14:16:19 Z glebustim Financial Report (JOI21_financial) C++17
0 / 100
 4000 ms 10952 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, n);
    for (int i = 0; i < n; ++i) {
        int c = 0;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] > a[i]) {
                ++c;
                if (c == d) {
                    r[i] = j;
                    break;
                }
            }
            else
                c = 0;
        }
    }
//    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 8536 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 3 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct
9 Correct 4 ms 8548 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 3 ms 8540 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 8644 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 8536 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 3 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct
9 Correct 4 ms 8548 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 3 ms 8540 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 8644 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 8536 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 3 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct
9 Correct 4 ms 8548 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 3 ms 8540 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 8644 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 Execution timed out 4046 ms 10944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 10952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8540 KB Output is correct
2 Correct 3 ms 8536 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 3 ms 8540 KB Output is correct
6 Correct 3 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct
9 Correct 4 ms 8548 KB Output is correct
10 Correct 3 ms 8540 KB Output is correct
11 Correct 3 ms 8540 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 8644 KB Output is correct
15 Incorrect 3 ms 8540 KB Output isn't correct
16 Halted 0 ms 0 KB -