Submission #415483

#	Time	Username	Problem	Language	Result	Execution time	Memory
415483		shivensinha4	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	2 ms	204 KiB

prison

#include "bits/stdc++.h"
#define int long long
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 = 1e14;
class SegmentTree {
private:
    vector<ii> tree; vi lazy; int n;
    ii bound = {-INF, 0};

    void push(int p, int c1, int c2) {
        lazy[c1] += lazy[p], lazy[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][0] += val;
            // cout << "...adding to " << l << " " << r << " -> " << tree[p][0] << 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]);
    }

    void setPoint(int i, int sec, int l, int r, int p) {
        if (l > i or r < i) return;
        if (l == r) {
            tree[p][1] = sec;
            return;
        }

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

        setPoint(i, sec, l, mid, c1); setPoint(i, sec, mid+1, r, c2);
        tree[p] = max(tree[c1], tree[c2]);
    }

    ii 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, bound); lazy.assign(4*n, 0);
    }

    ii mx(int i, int j) {
        return mx(i, j, 0, n-1, 0);
    }

    void rangeAdd(int i, int j, int val) {
        // cout << "adding to range " << i << " " << j << " -> " << val << endl;
        rangeAdd(i, j, val, 0, n-1, 0);
    }

    void setPoint(int i, int sec) {
        setPoint(i, sec, 0, n-1, 0);
    }
};


signed 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<ll> dp(n+1);
    vi ct(n+1);

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

    // ll mid = 0, ans;
    // cout << "testing " << mid << endl;
    // tree.build(n);
    // for (int i = n-1; i >= 0; i--) {
    // 	if (nums[i] <= t) {
    // 		tree.rangeAdd(i, i, INF+dp[i+1]);
    // 		tree.setPoint(i, -ct[i+1]);
    // 	}
    // 	for (auto j: revpt[i]) tree.rangeAdd(i, j-1, 1);
    // 	ii opt = tree.mx(i, n-1);
    // 	if (opt[0]-mid > 0) {
    // 		dp[i] = opt[0]-mid; ct[i] = -opt[1]+1;
    // 		cout << "hereee " << i << " " << opt[1] << endl;
    // 	} else {
    // 		dp[i] = 0; ct[i] = 0;
    // 	}
    // }

    // cout << mid << " -> " << (ct[0] <= d) << endl;
    // cout << "....... " << dp[0] << " " << ct[0] << endl;
    // if (ct[0] <= d) {
    // 	ans = mid;
    // 	// l = mid+1;
    // }
    // else r = mid;

    ll l = -1e10, r = +1e10, ans;
    vector<ll> fdp, fct;
    while (l <= r) {
        ll mid = l + (r - l)/2;
        tree.build(n);
        dp.assign(n+1, 0); ct.assign(n+1, 0);

        for (int i = n-1; i >= 0; i--) {
            if (nums[i] <= t) {
                tree.rangeAdd(i, i, INF+dp[i+1]);
                tree.setPoint(i, -ct[i+1]);
            }
            for (auto j: revpt[i]) tree.rangeAdd(i, j-1, 1);
            ii opt = tree.mx(i, n-1);
            if (opt[0]-mid > 0) {
                dp[i] = opt[0]-mid; ct[i] = -opt[1]+1;
                // cout << "hereee " << i << " " << opt[1] << endl;
            }
            // dp[i] = 0; ct[i] = 0;
            // }
        }

        // cout <<  l << " " << r << " " << mid << " -> fixed " << (dp[0] + (ct[0] * mid)) << " guys using " << ct[0] << endl;
        // cout << l << " " << r << " " << mid << " -> " << (ct[0] <= d) << endl;
        // cout << "....... " << dp[0] << " " << ct[0] << endl;
        if (ct[0] <= d) {
            // cout << "yaaaaas " << endl;
            fdp = dp, fct = ct;
            ans = mid;
            r = mid-1;
        }
        else l = mid+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, 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);
    // 	}
    // }

    int curr = 0;
    for_(i, 0, n) if (nums[i] <= t or pter[i] != -1) curr++;
    assert(curr >= (fdp[0] + (fct[0] * ans)));

    // cout << "fixed " << (dp[0] + (ct[0] * ans)) << " guys using " << ct[0] << endl;
    cout << curr-(fdp[0] + (fct[0] * ans)) << endl;
    // cout << curr-dp[0][d] << endl;
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:190:38: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  190 |     assert(curr >= (fdp[0] + (fct[0] * ans)));
      |                                      ^

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