제출 #1185961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185961		gyg	나일강 (IOI24_nile)	C++20	67 / 100	2093 ms	13640 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, 4 * N> tr;
    void intl() {
        tr.fill(-INF);
    }
    void upd(int i, int x, int u = 1, int lw = 1, int hg = n) {
        if (lw == hg) { tr[u] = x; return; }
        int md = (lw + hg) / 2;
        if (i <= md) upd(i, x, 2 * u, lw, md);
        else upd(i, x, 2 * u + 1, md + 1, hg);
        tr[u] = max(tr[2 * u], tr[2 * u + 1]);
    }
    int qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
        if (l > r) return -INF;
        if (l <= lw && hg <= r) return tr[u];
        int md = (lw + hg) / 2, ans = -INF;
        if (l <= md) ans = max(ans, qry(l, r, 2 * u, lw, md));
        if (r > md) ans = max(ans, qry(l, r, 2 * u + 1, md + 1, hg));
        return ans;
    }
};
arr<Sgt, 2> sgt;

arr<arr<int, 2>, N> dp;
void dp_cmp() {
    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();

    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: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18