Submission #940183

#	Time	Username	Problem	Language	Result	Execution time	Memory
940183		haxorman	Financial Report (JOI21_financial)	C++14	12 / 100	186 ms	19164 KiB

Main

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

#define int long long

const int mxN = 3e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
const int INF = 1e9 + 7;

int n, d, arr[mxN], seg[4*mxN], nex[mxN], dp[mxN];

void update(int ind, int val) {
    seg[ind+=SZ] = val;
    while (ind /= 2) {
        seg[ind] = max(seg[2*ind], seg[2*ind+1]);
    }
}

int query(int lo, int hi, int ind = 1, int l = 0, int r = SZ - 1) {
    if (lo > r || l > hi) {
        return -INF;
    }

    if (lo <= l && r <= hi) {
        return seg[ind];
    }

    int mid = (l+r)/2;
    return max(query(lo,hi,2*ind,l,mid), query(lo,hi,2*ind+1,mid+1,r));
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> d;
    
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    arr[n] = INT_MAX;
    
    vector<int> st = {n};
    for (int i = n-1; i >= 0; --i) {
        while (st.size() && arr[st.back()] <= arr[i]) {
            st.pop_back();
        }
        nex[i] = st.back();
        st.push_back(i);

        if (i < n-1) {
            update(i, -INF);
        }
    }
    update(n-1, 1);
    update(n, -INF);

    for (int i = n-2; i >= 0; --i) {
        dp[i] = max(query(nex[i], min(n, nex[i]+d-1)) + 1,
                   (query(i, i+d) ? 1ll : -1ll));

        update(i, (dp[i] < 0 ? -INF : dp[i]));
    }

    cout << query(0, n-1) << "\n";
}

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