Submission #1240552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240552		skibidi123	Financial Report (JOI21_financial)	C++20	19 / 100	266 ms	54376 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;

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 + 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);
    for(L+=coord.size(), R+=coord.size(); 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&i:a) cin>>i;
    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, {0,0});

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

    vector<pair<int,int>> f(n), q(n);
    int ix0 = get_idx(a[0]);
    f[0] = {-1, a[0]};
    q[0] = f[0];
    leaf[ix0].insert(f[0]);
    leaf[ix0].insert(q[0]);
    upd_leaf(ix0);
    for(int i=1;i<n;i++){
        int ix = get_idx(a[i]);
        if(i>d){
            int j = i-d-1;
            int ixj_f = get_idx(f[j].second);
            leaf[ixj_f].erase(leaf[ixj_f].find(f[j]));
            upd_leaf(ixj_f);
            int ixj_q = get_idx(q[j].second);
            leaf[ixj_q].erase(leaf[ixj_q].find(q[j]));
            upd_leaf(ixj_q);
        }
        f[i] = query(0, M);
        if(a[i]>f[i].second){
            f[i].first--;
            f[i].second = a[i];
        }
        leaf[get_idx(f[i].second)].insert(f[i]);
        upd_leaf(get_idx(f[i].second));

        if(ix>0){
            q[i] = query(0, ix);
            q[i].first--;
            q[i].second = a[i];
        } else {
            q[i] = {-1, a[i]};
        }
        leaf[ix].insert(q[i]);
        upd_leaf(ix);
    }
    cout<<max(-q[n-1].first,-f[n-1].first);
    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