Submission #1185960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185960		gyg	Nile (IOI24_nile)	C++20	17 / 100	2096 ms	7980 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed 
#define int long long
#define arr array 
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 1e5 + 5, INF = 1e18;

int n;
arr<pii, N> a;

arr<int, N> nr;
void nr_cmp(int d) {
    for (int i = 1; i <= n; i++) {
        int lw = 1, hg = i;
        while (lw < hg) {
            int md = (lw + hg) / 2;
            if (a[md].fir >= a[i].fir - d) hg = md;
            else lw = md + 1;
        }
        nr[i] = lw;
        // cout << i << ": " << nr[i] << '\n';
    }
}

struct Sgt {
    arr<int, N> tr;
    void intl() {
        tr.fill(-INF);
    }
    void upd(int i, int x) {
        tr[i] = x;
    }
    int qry(int l, int r) {
        if (l > r) return -INF;
        int ans = -INF;
        for (int i = l; i <= r; i++) ans = max(ans, tr[i]);
        return ans;
    }
};
arr<Sgt, 2> sgt;

arr<arr<int, 2>, N> dp;
void dp_cmp(int d) {
    sgt[0].intl(), sgt[1].intl();

    for (int i = 1; i <= n; i++) {
        for (int b : {0, 1}) {
            dp[i][b] = a[i].sec + ((b == 1) ? sgt[0].qry(1, i - 1) : sgt[1].qry(nr[i], i));
            if (b == 1) dp[i][b] = max(dp[i][b], a[i].sec);
            sgt[b].upd(i, dp[i][b]);
        }
    }
}

int slv(int d) {
    nr_cmp(d);
    dp_cmp(d);

    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[i][0]);
    return ans;
}

vec<int> calculate_costs(vec<sig> _ps, vec<sig> _fl, vec<sig> _pr, vec<sig> _qr) {
    n = _ps.size();
    int sm = 0;
    for (int i = 1; i <= n; i++) {
        a[i] = {_ps[i - 1], _fl[i - 1] - _pr[i - 1]};
        sm += _fl[i - 1];
    }
    sort(a.begin() + 1, a.begin() + n + 1);

    // for (int i = 1; i <= n; i++)
    //     cout << a[i].fir << " " << a[i].sec << '\n';

    vec<int> ans;
    for (int d : _qr)
        ans.push_back(sm - slv(d));
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 11 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18