Submission #420011

#	Time	Username	Problem	Language	Result	Execution time	Memory
420011		vkgainz	Financial Report (JOI21_financial)	C++17	100 / 100	623 ms	32724 KiB

Main

#include <bits/stdc++.h>
using namespace std;

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

int N, D;
Node comb(Node x, Node y) {
    Node ret;
    ret.pref = x.pref;
    if(x.pref == x.len)
        ret.pref = x.pref + y.pref;
    ret.suf = y.suf;
    if(y.suf == y.len)
        ret.suf = y.suf + x.suf;
    ret.val = max({x.val, y.val, x.suf + y.pref});
    ret.en = max(x.en, y.en);
    if(x.suf + y.pref >= D) {
        ret.en = max(ret.en, y.st + y.pref - 1);
    }
    ret.st = x.st;
    ret.len = x.len + y.len;
    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, 1};
            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);
        seg[x] = comb(seg[2 * x + 1], seg[2 * x + 2]);
    }
    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, 1};
           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, 0};
        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() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    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: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35