Submission #1170200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170200		Hamed_Ghaffari	Financial Report (JOI21_financial)	C++20	100 / 100	439 ms	25684 KiB

Main

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

using pii = pair<int, int>;

#define X first
#define Y second
#define maxs(a,b) (a=max(a,b))
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
#define pb push_back
#define all(x) x.begin(), x.end()
#define Mp make_pair

const int MXN = 3e5+5;

struct node {
    int pre, suf, ans;
    bool full;
    node(bool x=0): pre(x), suf(x), ans(x), full(x) {}
} seg[MXN<<2];
node operator+(node x, node y) {
    node res;
    res.pre = x.pre + (x.full ? y.pre : 0);
    res.suf = y.suf + (y.full ? x.suf : 0);
    res.ans = max({x.ans, y.ans, x.suf+y.pre});
    res.full = x.full&y.full;
    return res;
}
int n, d, a[MXN], ord[MXN], mx[MXN<<2];

void build(int l=0, int r=n, int id=1) {
    if(r-l == 1) {
        seg[id] = node(1);
        return;
    }
    build(l, mid, lc);
    build(mid, r, rc);
    seg[id] = seg[lc] + seg[rc];
}
void upd1(int p, int l=0, int r=n, int id=1) {
    if(r-l == 1) {
        seg[id] = seg[0];
        return;
    }
    p<mid ? upd1(p, l, mid, lc) : upd1(p, mid, r, rc);
    seg[id] = seg[lc] + seg[rc];
}
pair<int, node> find(int e, int l=0, int r=n, int id=1, node cur=seg[0]) {
    if(l>=e) return {l, cur};
    if(r<=e) {
        if((seg[id]+cur).ans<d) return {l, seg[id]+cur};
        if(r-l == 1) return {r, cur};
    }
    auto val = find(e, mid, r, rc, cur);
    return mid<val.X ? val : find(e, l, mid, lc, val.Y);
}
void upd2(int p, int x, int l=0, int r=n, int id=1) {
    if(r-l == 1) {
        maxs(mx[id], x);
        return;
    }
    p<mid ? upd2(p, x, l, mid, lc) : upd2(p, x, mid, r, rc);
    mx[id] = max(mx[lc], mx[rc]);
}
int get(int s, int e, int l=0, int r=n, int id=1) {
    if(s>=r || l>=e) return 0;
    if(s<=l && r<=e) return mx[id];
    return max(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> d;
    for(int i=0; i<n; i++) cin >> a[i], ord[i] = i;
    sort(ord, ord+n, [&](int i, int j) {
        return pii(a[i], -i) < pii(a[j], -j);
    });
    build();
    for(int t=0, i; t<n; t++) {
        i = ord[t];
        upd1(i);
        int pos = find(i).X;
        upd2(i, get(pos, i+1)+1);
    }
    cout << get(0, n) << '\n';
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35