Submission #668443

#	Time	Username	Problem	Language	Result	Execution time	Memory
668443		Kahou	Financial Report (JOI21_financial)	C++14	100 / 100	775 ms	28064 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 3e5 + 50;
int n, d;
pii a[N];
int seg[N<<2][2];
set<int> st;

void shift(int u) {
        int lc = u<<1;
        int rc = u<<1|1;
        seg[lc][0] = max(seg[lc][0], seg[u][0]);
        seg[rc][0] = max(seg[rc][0], seg[u][0]);
        seg[u][0] = 0;
}

void upd_DP(int l, int r, int x, bool flg, int u=1, int tl=1, int tr=n) {
        if (r < tl || tr < l) return;
        if (l <= tl && tr <= r) {
                return seg[u][0] = (flg? x: max(seg[u][0], x)), void();
        }
        shift(u);
        int md = (tl+tr)/2;
        int lc = u<<1;
        int rc = u<<1|1;
        upd_DP(l, r, x, flg, lc, tl, md);
        upd_DP(l, r, x, flg, rc, md+1, tr);
}
void upd_D(int id, int x, int u=1, int tl=1, int tr=n) {
        if (tl == tr) return seg[u][1] = x, void();
        shift(u);
        int md = (tl+tr)/2;
        int lc = u<<1;
        int rc = u<<1|1;
        if (id <= md) upd_D(id, x, lc, tl, md);
        else upd_D(id, x, rc, md+1, tr);
        seg[u][1] = max(seg[lc][1], seg[rc][1]);
}
int get_DP(int id, int u=1, int tl=1, int tr=n) {
        if (tl == tr) return seg[u][0];
        shift(u);
        int md = (tl+tr)/2;
        int lc = u<<1;
        int rc = u<<1|1;
        if (id <= md) return get_DP(id, lc, tl, md);
        else return get_DP(id, rc, md+1, tr);
}
int find_D(int l, int r, int u=1, int tl=1, int tr=n) { 
        if (r < tl || tr < l) return n+1;
        if (l <= tl && tr <= r && seg[u][1] <= d) return n+1;
        if (tl == tr) return tl;

        shift(u);
        int md = (tl+tr)/2;
        int lc = u<<1;
        int rc = u<<1|1;
        int t = find_D(l, r, lc, tl, md);
        if (t <= n) return t;
        else return find_D(l, r, rc, md+1, tr);
}

void solve() {
        cin >> n >> d;
        for (int i = 1; i <= n; i++) {
                cin >> a[i].F;
                a[i].S = -i;
        }
        sort(a+1, a+n+1);
        for (int i = 1; i <= n; i++) {
                int id = -a[i].S;
                int prv = (st.lower_bound(id) == st.begin()? -n: *prev(st.lower_bound(id)));
                int nxt = (st.lower_bound(id) == st.end()? n+1 : *st.lower_bound(id));
                int t = (id-prv <= d? get_DP(prv)+1: 1);
                upd_DP(id, id, t, 1);
                upd_D(id, id-prv);
                if (nxt <= n) upd_D(nxt, nxt-id);
                upd_DP(id, find_D(id+1, n)-1, t, 0);
                st.insert(id);
        }

        cout << get_DP(n) << endl;
}
int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

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