Submission #415482

#	Time	Username	Problem	Language	Result	Execution time	Memory
415482		shivensinha4	The short shank; Redemption (BOI21_prison)	C++17	55 / 100	775 ms	524292 KiB

prison

#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'

int INF = 1e7;
class SegmentTree {
private:
    vi tree, lazy; int n;
    int bound = -INF;

    void push(int p, int c1, int c2) {
        lazy[c1] += lazy[p], lazy[c2] += lazy[p];
        tree[c1] += lazy[p], tree[c2] += lazy[p];
        lazy[p] = 0;
    }

    void rangeAdd(int i, int j, int val, int l, int r, int p) {
        if (l > j or r < i) return;
        if (l >= i and r <= j) {
            lazy[p] += val; tree[p] += val;
//            cout << l << " " << r << " added " << val << " max is now " << tree[p] << endl;
            return;
        }

        int mid = (l + r) / 2;
        int c1 = 2*p+1, c2 = 2*p+2;
        if (lazy[p]) push(p, c1, c2);

        rangeAdd(i, j, val, l, mid, c1); rangeAdd(i, j, val, mid+1, r, c2);
        tree[p] = max(tree[c1], tree[c2]);
    }

    int mx(int i, int j, int l, int r, int p) {
        if (l > j or r < i) return bound;
        if (l >= i and r <= j) return tree[p];

        int mid = (l + r) / 2;
        int c1 = 2*p+1, c2 = 2*p+2;
        if (lazy[p]) push(p, c1, c2);
        return max(mx(i, j, l, mid, c1), mx(i, j, mid+1, r, c2));
    }

public:
    void build(int N) {
        n = N;
        tree.assign(4*n, -INF); lazy.assign(4*n, 0);
    }

    int mx(int i, int j) {
        int ans = mx(i, j, 0, n-1, 0);
//        cout << "max from " << i << " ... " << j << " -> " << ans << endl;
        return ans;
    }

    void rangeAdd(int i, int j, int val) {
//        cout << "asking tree to add " << val << " from " << i << " ... " << j << endl;
        rangeAdd(i, j, val, 0, n-1, 0);
    }
};


int main() {
#ifdef mlocal
    freopen("test.in", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, d; ll t; cin >> n >> d >> t;
    vector<ll> nums(n);
    for_(i, 0, n) cin >> nums[i];
    vi pter(n, -1);
    stack<int> st;
    for_(i, 0, n) {
        while (st.size() and nums[st.top()]+i-st.top() > t) st.pop();

        if (nums[i] <= t) {
            while (st.size() and nums[st.top()]-st.top() >= nums[i]-i) st.pop();
            st.push(i);
        } else if (st.size()) pter[i] = st.top();
    }

    vector<vi> revpt(n);
    for_(i, 0, n) if (pter[i] != -1) revpt[pter[i]].push_back(i);

    vector<vi> dp(n+1, vi(d+1));

    SegmentTree tree;
    tree.build(n);
    tree.rangeAdd(0, 1, INF); tree.rangeAdd(0, 1, INF);
//    cout << "...." << tree.mx(0, n-1) << endl;

    for_(k, 1, d+1) {
        tree.build(n);
        for (int i = n-1; i >= 0; i--) {
            if (nums[i] <= t) {
                tree.rangeAdd(i, i, INF+dp[i+1][k-1]);
            }
            for (auto j: revpt[i]) tree.rangeAdd(i, j-1, 1);
            dp[i][k] = tree.mx(i, n-1);
        }
     }

//     for_(k, 1, d+1) {
//     	tree.build(n);
//     	for (int i = n-1; i >= 0; i--) {
//     		if (nums[i] <= t) {
//     			tree.rangeAdd(i, i, tree.mx(i, i)+dp[i+1][k-1]);
//     		}
//     		for (auto j: revpt[i]) tree.rangeAdd(i, j-1, 1);
//     		// int mx = 0;
//     		// for_(j, i, n) mx = max(mx, effect[j]+dp[j+1][k-1]);
//     		dp[i][k] = tree.mx(i, n-1);
//     	}
//     }

    int curr = 0;
    for_(i, 0, n) if (nums[i] <= t or pter[i] != -1) curr++;

    cout << curr-dp[0][d] << endl;
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20