제출 #1167882

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

Main

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

#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()

const int MXN = 3e5+5;

int N, mx[MXN<<2], mxpos[MXN<<2], lz[MXN<<2];

inline void apply(int x, int id) {
    mxpos[id] = x;
    lz[id] = x;
}
inline void shift(int l, int r, int id) {
    if(r-l>1 && lz[id]) {
        apply(lz[id], lc);
        apply(lz[id], rc);
    }
    lz[id] = 0;
}
void upd(int s, int e, int x, int l=0, int r=N, int id=1) {
    shift(l, r, id);
    if(s<=l && r<=e) {
        apply(x, id);
        return;
    }
    if(s<mid) upd(s, e, x, l, mid, lc);
    if(e>mid) upd(s, e, x, mid, r, rc);
    mxpos[id] = max(mxpos[lc], mxpos[rc]);
}
void modify(int p, int x, int l=0, int r=N, int id=1) {
    if(r-l == 1) {
        maxs(mx[id], x);
        return;
    }
    p<mid ? modify(p, x, l, mid, lc) : modify(p, x, mid, r, rc);
    mx[id] = max(mx[lc], mx[rc]);
}
int find(int x, int l=0, int r=N, int id=1) {
    shift(l, r, id);
    if(mxpos[id]<x) return -1;
    if(r-l==1) return l;
    int res = find(x, l, mid, lc);
    return res==-1 ? find(x, mid, r, rc) : res;
}
int get(int s, int e, int l=0, int r=N, int id=1) {
    if(s<=l && r<=e) return mx[id];
    if(e<=mid) return get(s, e, l, mid, lc);
    if(s>=mid) return get(s, e, mid, r, rc);
    return max(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}

int n, d, a[MXN];
vector<int> cmp;

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> d;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        cmp.pb(a[i]);
    }
    sort(all(cmp));
    cmp.resize(unique(all(cmp))-cmp.begin());
    N = cmp.size();
    for(int i=1; i<=n; i++) {
        a[i] = lower_bound(all(cmp), a[i])-cmp.begin();
        int pos = find(i-d);
        if(pos!=-1 && pos<a[i])
            modify(a[i], get(pos, a[i])+1);
        else modify(a[i], 1);
        upd(a[i], N, i);
    }
    cout << get(find(n), N) << '\n';
    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