Submission #1261538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261538		software1146	Nile (IOI24_nile)	C++20	100 / 100	139 ms	23920 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back

const ll INF = 1e17;
ll n, q;
vc<ll> w, a, b, ques, res;
ll ans = 0;
vc<ll> sum, par, be, beg, bo, bog;
set<ll> seg;
struct Event {
        ll d, t, i;
};
vc<Event> events;
void sortItems() {
        vc<ll> ord(n);
        iota(all(ord), 0);
        sort(all(ord), [&](ll i, ll j) {
                return w[i] < w[j];
        });
        vc<ll> tmp(n);
        for (ll i = 0; i < n; i++)
                tmp[i] = w[ord[i]];
        swap(tmp, w);
        for (ll i = 0; i < n; i++)
                tmp[i] = a[ord[i]];
        swap(tmp, a);
        for (ll i = 0; i < n; i++)
                tmp[i] = b[ord[i]];
        swap(tmp, b);
}
ll total(ll i) {
        if (par[i] == 0)
                return sum[i];
        else
                return sum[i] + min(be[i], bog[i]);
}
void init() {
        sum = b;
        par.assign(n, 1);
        be.resize(n);
        for (ll i = 0; i < n; i++)
                be[i] = a[i] - b[i];
        beg.assign(n, INF);
        bo = bog = beg;
        for (ll i = 0; i <= n; i++)
                seg.insert(i);
        ans = 0;
        for (ll i = 0; i < n; i++)
                ans += total(i);
        res.resize(q);
}
void merge(ll i) {
        ll x = *(--seg.upper_bound(i));
        ll y = i + 1;
        ans -= total(x) + total(y);
        sum[x] += sum[y];
        if (par[x] == 0) {
                be[x] = min(be[x], be[y]);
                beg[x] = min(beg[x], beg[y]);
                bo[x] = min(bo[x], bo[y]);
                bog[x] = min(bog[x], bog[y]);
        } else {
                be[x] = min(be[x], bo[y]);
                beg[x] = min(beg[x], bog[y]);
                bo[x] = min(bo[x], be[y]);
                bog[x] = min(bog[x], beg[y]);
        }
        par[x] ^= par[y];
        ans += total(x);
        seg.erase(i + 1);
}
void makeGood(ll i) {
        ll l = *(--seg.upper_bound(i));
        ans -= total(l);
        if ((i - l) % 2 == 0)
                beg[l] = min(beg[l], a[i] - b[i]);
        else
                bog[l] = min(bog[l], a[i] - b[i]);
        ans += total(l);
}
void handle(Event &event) {
        if (event.t == 0)
                merge(event.i);
        else if (event.t == 1)
                makeGood(event.i);
        else
                res[event.i] = ans;
}
void sweep() {
        events.reserve(n - 1 + n - 2 + q);
        for (ll i = 0; i + 1 < n; i++)
                events.pub({w[i + 1] - w[i], 0, i});
        for (ll i = 0; i + 2 < n; i++)
                events.pub({w[i + 2] - w[i], 1, i + 1});
        for (ll i = 0; i < q; i++)
                events.pub({ques[i], 2, i});
        sort(all(events), [&](auto &x, auto &y) {
                if (x.d != y.d)
                        return x.d < y.d;
                if (x.t != y.t)
                        return x.t < y.t;
                return x.i < y.i;
        });
        for (auto &event : events)
                handle(event);
}
void program() {
        sortItems();
        init();
        sweep();
}
vc<ll> calculate_costs(vc<int> W, vc<int> A, vc<int> B, vc<int> E) {
        n = sz(W);
        q = sz(E);
        w.assign(all(W));
        a.assign(all(A));
        b.assign(all(B));
        ques.assign(all(E));
        program();
        return res;
}

• 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