Submission #906107

#	Time	Username	Problem	Language	Result	Execution time	Memory
906107		hmm789	Financial Report (JOI21_financial)	C++14	100 / 100	746 ms	106832 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 998244353

struct node1 {
    int s, e, m, v;
    node1 *l, *r;
    node1(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2, v = -INF;
        if(s != e) {
            l = new node1(s, m);
            r = new node1(m+1, e);
        }
    }
    void update(int x, int val) {
        if(s == e) {v = val; return;}
        else if(x > m) r->update(x, val);
        else l->update(x, val);
        v = max(l->v, r->v);
    }
    int query(int x) {
        if(s == e) return s;
        if(l->v > x) return l->query(x);
        else if(r->v > x) return r->query(x);
        else return e;
    }
} *root1;

struct node2 {
    int s, e, m, v, lz;
    node2 *l, *r;
    node2(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2, v = 1, lz = -1;
        if(s != e) {
            l = new node2(s, m);
            r = new node2(m+1, e);
        }
    }
    void prop() {
        if(lz == -1) return;
        v = max(v, lz);
        if(s != e) {
            l->lz = max(l->lz, lz);
            r->lz = max(r->lz, lz);
        }
        lz = -1;
    }
    void update(int x, int y, int val) {
        prop();
        if(x <= s && e <= y) {lz = max(lz, val); return;}
        else if(x > m) r->update(x, y, val);
        else if(y <= m) l->update(x, y, val);
        else l->update(x, y, val), r->update(x, y, val);
        l->prop(); r->prop();
        v = max(l->v, r->v);
    }
    int query(int x) {
        prop();
        if(s == e) return v;
        else if(x > m) return r->query(x);
        else return l->query(x);
    }
} *root2;

bool cmp(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first) return a.first < b.first;
    else return a.second > b.second;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, d, ans = 0;
    cin >> n >> d;
    int a[n], r[n], tr[n], dp[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    multiset<int> s;
    root1 = new node1(0, n-1);
    for(int i = 0; i < n; i++) {
        s.insert(a[i]);
        if(i >= d) s.erase(s.find(a[i-d]));
        tr[i] = *s.begin();
    }
    for(int i = n-1; i >= 0; i--) {
        if(i+d < n) root1->update(i+d, tr[i+d]);
        r[i] = root1->query(a[i]);
    }
    pair<int, int> ord[n];
    for(int i = 0; i < n; i++) {
        ord[i] = {a[i], i};
    }
    sort(ord, ord+n, cmp);
    root2 = new node2(0, n-1);
    for(int i = 0; i < n; i++) {
        int idx = ord[i].second;
        dp[idx] = root2->query(idx);
        root2->update(idx, r[idx], dp[idx]+1);
        ans = max(ans, dp[idx]);
    }
    cout << ans;
}

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