oj.uz

답안 #420005

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
420005 2021-06-07T21:43:37 Z vkgainz Financial Report (JOI21_financial) C++17
5 / 100
 693 ms 28488 KB 
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int pref, suf, val, en, st;
};

int N, D;
Node comb(Node x, Node y) {
    Node ret;
    ret.pref = x.pref;
    ret.val = max({x.val, y.val, x.suf + y.pref});
    ret.suf = y.suf;
    ret.en = max(x.en, y.en);
    ret.st = x.st;
    if(x.suf + y.pref >= D) {
        ret.en = max(ret.en, y.st + y.pref - 1);
    }
    return ret;
}
    

struct seg_tree {
    vector<Node> seg;
    int sz;
    void build(int x, int lx, int rx) {
        if(rx - lx == 1) {
            seg[x] = {1, 1, 1, -1, lx};
            if(1 >= D) seg[x].en = lx;
            return;
        }
        int m = (lx + rx) / 2;
        build(2 * x + 1, lx, m);
        build(2 * x + 2, m, rx);
    }
    void init(int N) {
        sz = 1;
        while(sz < N) sz *= 2;
        seg.resize(2 * sz);
        build(0, 0, sz);
    }
    void upd(int i, int x, int lx, int rx) {
        if(rx - lx == 1) {
           seg[x] = {0, 0, 0, -1, lx};
           return;
        }
        int m = (lx + rx) / 2;
        if(i < m) upd(i, 2 * x + 1, lx, m);
        else upd(i, 2 * x + 2, m, rx);
        seg[x] = comb(seg[2 * x + 1], seg[2 * x + 2]);
    }
    void upd(int i) { upd(i, 0, 0, sz); }
    Node query(int l, int r, int x, int lx, int rx) {
        if(lx >= r || rx <= l) return {0, 0, 0, -1, lx};
        if(lx >= l && rx <= r) {
            return seg[x];
        }
        int m = (lx + rx) / 2;
        return comb(query(l, r, 2 * x + 1, lx, m), query(l, r, 2 * x + 2, m, rx));
    }
    Node query(int l, int r) { return query(l, r, 0, 0, sz); }
} in;

struct mx_tree {
    vector<int> seg;
    int sz;
    void init(int N) {
        sz = 1;
        while(sz < N) sz *= 2;
        seg.resize(2 * sz);
    }
    void upd(int i, int v, int x, int lx, int rx) {
        if(rx - lx == 1) {
            seg[x] = v;
            return;
        }
        int m = (lx + rx) / 2;
        if(i < m) upd(i, v, 2 * x + 1, lx, m);
        else upd(i, v, 2 * x + 2, m, rx);
        seg[x] = max(seg[2 * x + 1], seg[2 * x + 2]);
    }
    void upd(int i, int v) { upd(i, v, 0, 0, sz); }
    int query(int l, int r, int x, int lx, int rx) {
        if(lx >= r || rx <= l) return 0;
        if(lx >= l && rx <= r) return seg[x];
        int m = (lx + rx) / 2;
        return max(query(l, r, 2 * x + 1, lx, m), query(l, r, 2 * x + 2, m, rx));
    }
    int query(int l, int r) { return query(l, r, 0, 0, sz); }
} to_query;

int main() {
    cin >> N >> D;
    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector<pair<int, int>> ord(N);
    for(int i = 0; i < N; i++) {
        ord[i] = {A[i], -i};
    }
    sort(ord.begin(), ord.end());
    int ans = 0;
    in.init(N), to_query.init(N);
    for(int i = 0; i < N; i++) {
        int idx = -ord[i].second;
        in.upd(idx);
        int lst = in.query(0, idx + 1).en;
        int curr = to_query.query(lst + 1, idx) + 1;
        ans = max(ans, curr);
        to_query.upd(idx, curr);
    }
    cout << ans << "\n";
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 496 ms 28336 KB Output is correct
2 Correct 524 ms 28348 KB Output is correct
3 Incorrect 641 ms 28432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 519 ms 28432 KB Output is correct
2 Correct 654 ms 28436 KB Output is correct
3 Correct 693 ms 28484 KB Output is correct
4 Correct 687 ms 28344 KB Output is correct
5 Correct 630 ms 28436 KB Output is correct
6 Correct 685 ms 28488 KB Output is correct
7 Correct 468 ms 28432 KB Output is correct
8 Correct 494 ms 28480 KB Output is correct
9 Correct 496 ms 28408 KB Output is correct
10 Correct 575 ms 28368 KB Output is correct
11 Correct 663 ms 28436 KB Output is correct
12 Correct 605 ms 28460 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -