제출 #1240534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240534		skibidi123	Financial Report (JOI21_financial)	C++20	19 / 100	285 ms	54392 KiB

Main

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

int n, d;
vector<int> a, coord;
vector<multiset<pair<int,int>>> leaf;
vector<pair<int,int>> st;

// so sánh lex (first, sau đó second)
inline pair<int,int> mn(const pair<int,int>& A, const pair<int,int>& B){
    return (A < B ? A : B);
}

void upd_leaf(int idx){
    pair<int,int> v = leaf[idx].empty() ? make_pair(0,0) : *leaf[idx].begin();
    int p = idx + (int)coord.size();
    st[p] = v;
    for(p >>= 1; p; p >>= 1)
        st[p] = mn(st[p<<1], st[p<<1|1]);
}

pair<int,int> query(int L, int R){
    pair<int,int> res = make_pair(0,0);
    int N = coord.size();
    for(L += N, R += N; L < R; L >>= 1, R >>= 1){
        if(L & 1) res = mn(res, st[L++]);
        if(R & 1) res = mn(res, st[--R]);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    a.resize(n);
    for(int &x : a) cin >> x;
    coord = a;
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    int M = coord.size();

    leaf.assign(M, {});
    st.assign(2*M, make_pair(0,0));

    auto idx_of = [&](int x){
        return int(lower_bound(coord.begin(), coord.end(), x) - coord.begin());
    };

    vector<pair<int,int>> f(n), q(n);
    int ix0 = idx_of(a[0]);
    f[0] = {-1, a[0]};
    q[0] = f[0];
    leaf[ix0].insert(f[0]);
    leaf[ix0].insert(q[0]);
    upd_leaf(ix0);
    int ans = 1;

    for(int i = 1; i < n; i++){
        int ix = idx_of(a[i]);
        if(i > d){
            int j = i - d - 1;
            int ixj_f = idx_of(f[j].second);
            leaf[ixj_f].erase(leaf[ixj_f].find(f[j]));
            upd_leaf(ixj_f);
            int ixj_q = idx_of(q[j].second);
            leaf[ixj_q].erase(leaf[ixj_q].find(q[j]));
            upd_leaf(ixj_q);
        }

        // case1: kéo chuỗi tốt nhất bất kể giá trị cuối
        f[i] = query(0, M);
        if(a[i] > f[i].second){
            f[i].first--;
            f[i].second = a[i];
        }
        ans = max(ans, -f[i].first);
        leaf[idx_of(f[i].second)].insert(f[i]);
        upd_leaf(idx_of(f[i].second));

        // case2: chỉ lấy những dãy có last < a[i]
        if(ix > 0){
            q[i] = query(0, ix);
            q[i].first--;
            q[i].second = a[i];
        } else {
            q[i] = {-1, a[i]};
        }
        ans = max(ans, -q[i].first);
        leaf[ix].insert(q[i]);
        upd_leaf(ix);
    }

    cout << ans;
    return 0;
}

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