Submission #1293849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293849		bon_voyage	Nile (IOI24_nile)	C++17	100 / 100	114 ms	17252 KiB

nile

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Block {
    ll sum, ans;
    int odd, even, len, T[2];
};

struct Node {
    int w, a, b;
};

struct Query {
    int d, id;
};

const int MAXN = 100000 + 5;
const int INF = 0x3f3f3f3f;

Block c[MAXN];
Node a[MAXN];
Query q[MAXN], p[MAXN], r[MAXN];
int n, h_[MAXN], t_[MAXN];

bool cmpQ(const Query &x, const Query &y) { return x.d < y.d; }
bool cmpNode(const Node &x, const Node &y) { return x.w < y.w; }

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int Q = (int)E.size();
    n = (int)W.size();
    ll ans = 0;

    for (int i = 0; i < n; i++) {
        a[i + 1] = {W[i], A[i], B[i]};
        ans += A[i];
    }
    for (int i = 0; i < Q; i++) {
        q[i + 1] = {E[i], i + 1};
    }

    sort(a + 1, a + n + 1, cmpNode);
    sort(q + 1, q + Q + 1, cmpQ);

    set<int> se;
    for (int i = 1; i <= n; i++) {
        t_[i] = h_[i] = i;
        c[i].sum = a[i].b;
        c[i].ans = a[i].a;
        c[i].odd = a[i].a - a[i].b;
        c[i].even = INF;
        c[i].len = 1;
        c[i].T[0] = c[i].T[1] = INF;
        se.insert(i);
    }

    int ct = 0;
    for (int i = 2; i < n; i++) {
        p[++ct] = {a[i + 1].w - a[i - 1].w, i};
    }
    for (int i = 1; i < n; i++) {
        r[i] = {a[i + 1].w - a[i].w, i};
    }

    sort(p + 1, p + ct + 1, cmpQ);
    sort(r + 1, r + n, cmpQ);

    vector<long long> R(Q, 0);
    int p1 = 1, p2 = 1;

    for (int i = 1; i <= Q; i++) {
        int D = q[i].d;

        while (p1 < n && r[p1].d <= D) {
            int u = r[p1].id;
            int b1 = h_[u];
            int b2 = u + 1;

            c[b1].sum += c[b2].sum;
            c[b1].T[0] = min(c[b1].T[0], c[b2].T[0]);
            c[b1].T[1] = min(c[b1].T[1], c[b2].T[1]);

            ans -= c[b1].ans + c[b2].ans;

            if ((c[b1].len + c[b2].len) % 2 == 0) {
                c[b1].ans = c[b1].sum;
                ans += c[b1].sum;
            } else {
                ll res = c[b1].ans + c[b2].ans;
                if (c[b1].len % 2 == 1) {
                    res = min(res, c[b1].sum + c[b2].even);
                } else {
                    res = min(res, c[b1].sum + c[b1].odd);
                }
                res = min(res, c[b1].sum + c[b1].T[!(b1 % 2)]);
                c[b1].ans = res;
                ans += res;
            }

            if (c[b1].len % 2 == 1) {
                swap(c[b2].odd, c[b2].even);
            }
            c[b1].odd = min(c[b1].odd, c[b2].odd);
            c[b1].even = min(c[b1].even, c[b2].even);
            c[b1].len += c[b2].len;

            h_[t_[b2]] = b1;
            t_[b1] = t_[b2];
            se.erase(b2);

            p1++;
        }

        while (p2 <= ct && p[p2].d <= D) {
            int u = p[p2].id;
            auto it = se.upper_bound(u);
            --it;
            int head = *it;

            c[head].T[u % 2] = min(c[head].T[u % 2], a[u].a - a[u].b);

            ans -= c[head].ans;
            if (c[head].len % 2 == 1) {
                c[head].ans = min(c[head].ans, c[head].sum + c[head].T[!(head % 2)]);
            }
            ans += c[head].ans;

            p2++;
        }

        R[q[i].id - 1] = ans;
    }

    return R;
}

• 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: 15 / 15
• Subtask 7: 18 / 18