Submission #427729

#	Time	Username	Problem	Language	Result	Execution time	Memory
427729		keko37	The short shank; Redemption (BOI21_prison)	C++14	70 / 100	2078 ms	83396 KiB

prison

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <llint, llint> pi;

const int MAXN = 2000005;
const int sign = -1;
const llint INF = 1000000000000000000LL;

int n, k, T, ofs = 1, cnt;
int t[MAXN], lim[MAXN], add[MAXN];
llint mx[75005 * 4], prop[75005 * 4], br[75005 * 4];
pi dp[MAXN];
set <int> st;
vector <int> v[MAXN];

void build () {
    for (int i = 1; i <= n; i++) {
        int j = i + T - t[i];
        if (i <= j) {
            st.insert(i);
            if (j + 1 <= n) v[j + 1].push_back(i);
        }
        for (auto x : v[i]) {
            st.erase(x);
        }
        if (!st.empty()) {
            lim[i] = *st.rbegin();
            if (lim[i] < i) add[lim[i]]++;
            cnt++;
        } else {
            lim[i] = 1e9;
        }
        //cout  << "bla " << i << " " << lim[i] << endl;
    }
}

void upd (int x, pi novi) {
    x += ofs;
    mx[x] = novi.first;
    br[x] = novi.second;
    x /= 2;
    while (x > 0) {
        pi lef = {mx[2 * x] + prop[2 * x], br[2 * x]};
        pi rig = {mx[2 * x + 1] + prop[2 * x + 1], br[2 * x + 1]};
        pi res = max(lef, rig);
        mx[x] = res.first;
        br[x] = res.second;
        x /= 2;
    }
    /*cout << "ispis " << x << endl;
    for (int i = 0; i < 2 * ofs; i++) {
        cout << "bla " << i << " " << mx[i] << endl;
    }*/
}

pi update (int x, int from, int to, int lo, int hi) {
    if (from <= lo && hi <= to) {
        prop[x] += 1;
        return {mx[x] + prop[x], br[x]};
    }
    if (to < lo || hi < from) return {mx[x] + prop[x], br[x]};
    pi lef = update(2 * x, from, to, lo, (lo + hi) / 2);
    pi rig = update(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi);
    pi res = max(lef, rig);
    mx[x] = res.first;
    br[x] = res.second;
    return {mx[x] + prop[x], br[x]};
}

pi calc (llint cost) {
    for (int i = 0; i < 2 * ofs; i++) {
        mx[i] = -INF; br[i] = -INF;
        prop[i] = 0;
    }
    upd(0, {0, 0});
    pi res = {0, 0};
    int curr = 0;
    for (int i = 1; i <= n; i++) {
        curr += add[i];
        if (lim[i] < i) {
            update(1, lim[i], i - 1, 0, ofs - 1);
            curr--;
        }
        //cout << "sad na " << i << " " << mx[1] << endl;
        dp[i] = {mx[1] + curr - cost, br[1] + sign};
        upd(i, {dp[i].first - curr, dp[i].second});
        res = max(res, dp[i]);
    }
    return res;
}

llint bs () {
    llint lo = 0, hi = 1e9;
    while (lo < hi) {
        llint mid = (lo + hi) / 2;
        pi res = calc(mid);
        if (sign * res.second > k) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    //cout << "lo je " << lo << endl;
    pi res = calc(lo);
    return res.first + lo * k;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> T;
    while (ofs < n + 1) ofs *= 2;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    build();
    pi res = calc(3);
    //cout << res.first << " " << res.second;
    cout << cnt - bs();
    /*for (ld i = 0; i < 10; i += 0.1) {
        pi res = calc(i);
        cout << "bla " << i << "  " << res.first << " " << sign * res.second << endl;
    }*/
    return 0;
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:120:8: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  120 |     pi res = calc(3);
      |        ^~~

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