Submission #1242856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242856		hanifchdn	Nile (IOI24_nile)	C++20	100 / 100	143 ms	19372 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 1e5 + 5;
const ll inf = 1e18;

struct segtree {
    ll st[4 * N];

    void build(int x, int tl, int tr) {
        if (tl == tr) st[x] = inf;
        else {
            int tm = (tl + tr) / 2;
            build(2 * x, tl, tm);
            build(2 * x + 1, tm + 1, tr);
            st[x] = inf;
        }
    }

    void update(int x, int tl, int tr, int i, ll val) {
        if (tl == tr) st[x] = val;
        else {
            int tm = (tl + tr) / 2;
            if (i <= tm) update(2 * x, tl, tm, i, val);
            else update(2 * x + 1, tm + 1, tr, i, val);
            st[x] = min(st[2 * x], st[2 * x + 1]);
        }
    }

    ll get(int x, int tl, int tr, int l, int r) {
        if (tr < l or r < tl) return inf;
        if (l <= tl and tr <= r) return st[x];
        int tm = (tl + tr) / 2;
        return min(get(2 * x, tl, tm, l, r), get(2 * x + 1, tm + 1, tr, l, r));
    }
} st1, st2;

ll par[N], sum[N], len[N], rg[N];

int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    par[y] = x;
    sum[x] += sum[y];
    len[x] += len[y];
    rg[x] = rg[y];
}

vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) {
    int n = (int)w.size(), q = (int)e.size();
    vector<pll> at, qt;
    vector<ll> ans(q);
    for (int i = 0; i < n; i++) at.push_back({w[i], i});
    for (int i = 0; i < q; i++) qt.push_back({e[i], i});
    sort(at.begin(), at.end());
    sort(qt.begin(), qt.end());
    ll res = 0;
    st1.build(1, 0, n - 1);
    st2.build(1, 0, n - 1);
    for (int i = 0; i < n; i++) {
        int id = at[i].se;
        if (i % 2) st2.update(1, 0, n - 1, i, a[id] - b[id]);
        else st1.update(1, 0, n - 1, i, a[id] - b[id]);
        par[i] = i, len[i] = 1;
        rg[i] = i, sum[i] = b[id];
        res += a[id];
    }
    priority_queue<pll> pq1, pq2;
    for (int i = 0; i < n - 1; i++) {
        pq1.push({-(at[i + 1].fi - at[i].fi), i});
    }
    for (int i = 1; i < n - 1; i++) {
        pq2.push({-(at[i + 1].fi - at[i - 1].fi), i});
    }
    for (int i = 0; i < q; i++) {
        while (!pq1.empty() and -pq1.top().fi <= qt[i].fi) {
            int x = pq1.top().se, y = x + 1;
            pq1.pop();
            x = find(x), y = find(y);
            res -= sum[x] + sum[y];
            if (len[x] % 2) {
                if (x % 2) res -= st2.get(1, 0, n - 1, x, rg[x]);
                else res -= st1.get(1, 0, n - 1, x, rg[x]);
            }
            if (len[y] % 2) {
                if (y % 2) res -= st2.get(1, 0, n - 1, y, rg[y]);
                else res -= st1.get(1, 0, n - 1, y, rg[y]);      
            }      
            merge(x, y);
            res += sum[x];
            if (len[x] % 2) {
                if (x % 2) res += st2.get(1, 0, n - 1, x, rg[x]);
                else res += st1.get(1, 0, n - 1, x, rg[x]);
            }
        }
        while (!pq2.empty() and -pq2.top().fi <= qt[i].fi) {
            int x = pq2.top().se;
            pq2.pop();
            int px = find(x);
            if (len[px] % 2) {
                if (px % 2) res -= st2.get(1, 0, n - 1, px, rg[px]);
                else res -= st1.get(1, 0, n - 1, px, rg[px]);
            }
            int id = at[x].se;
            st1.update(1, 0, n - 1, x, a[id] - b[id]);
            st2.update(1, 0, n - 1, x, a[id] - b[id]);
            if (len[px] % 2) {
                if (px % 2) res += st2.get(1, 0, n - 1, px, rg[px]);
                else res += st1.get(1, 0, n - 1, px, rg[px]);
            }
        }
        ans[qt[i].se] = res;
    }
    return ans;
}

/*
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5
9
1

5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
1
5

*/

• 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