제출 #921450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
921450		AverageAmogusEnjoyer	Financial Report (JOI21_financial)	C++17	19 / 100	330 ms	36980 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
constexpr int nax = 300300;
int n,d;
int a[nax];
int b[nax];
int dp[nax];
int st[4*nax];
multiset<int> s[nax];
void upd(int p,int x,int u=1,int tl=0,int tr=nax) {
    if (tl == tr) {
        st[u] = x;
        return;
    }
    int mid=(tl+tr)/2;
    if (p <= mid) {
        upd(p,x,2*u,tl,mid);
    } else {
        upd(p,x,2*u+1,mid+1,tr);
    }
    st[u] = max(st[2*u],st[2*u+1]);
}
int qry(int l,int r,int u=1,int tl=0,int tr=nax) {
    if (l > r) { return 0; }
    if (l == tl && r == tr) {
        return st[u];
    }
    int mid=(tl+tr)/2;
    return max(qry(l,min(r,mid),2*u,tl,mid),qry(max(mid+1,l),r,2*u+1,mid+1,tr));
}
int main() {
    cin >> n >> d;
    for (int i=0;i<n;i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b,b+n);
    for (int i=0;i<n;i++) {
        a[i] = lower_bound(b,b+n,a[i])-b;
    }
    int mx = 0;
    auto rmn = [&](int l,int r) {
        int R = nax;
        for (;l<=r;l++) {
            cmin(R,a[l]);
        }
        return R;
    };
    for (int i=0;i<n;i++) {
        if (i > d) {
            int w = a[i-d-1];
            
            if (rmn(i-d,i) > w) {
                auto it = s[w].find(dp[i-d-1]);
                assert(it!=s[w].end());
                s[w].erase(it);
                upd(w,(s[w].empty() ? 0 : *s[w].rbegin()));
                // cout << "erased " << i-d-1 << endl;
            } else {
                // cout << "didnt erase " << i-d-1 << endl;
            }
        }
        int w = a[i];
        int c = qry(0,w-1)+1;
        s[w].insert(c);
        upd(w,*s[w].rbegin());
        dp[i] = c;
        cmax(mx,dp[i]);
        // cout << c << endl;
    }
    cout << mx << endl;
}

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