Submission #1192590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192590		Nelt	Nile (IOI24_nile)	C++20	100 / 100	157 ms	25480 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
struct SegTree
{
    ll n;
    vector<ll> st;
    SegTree(ll sz = 0, bool input = false)
    {
        n = sz;
        st.resize((n + 1) << 1, -1e10);
    }
    void set(ll i, ll val)
    {
        st[i + n - 1] = val;
    }
    void build()
    {
        for (ll i = n - 1; i >= 1; i--)
            st[i] = max(st[i << 1], st[i << 1 | 1]);
    }
    void modify(ll p, ll val)
    {
        for (st[p += n - 1] = val; p > 1; p >>= 1)
            st[p >> 1] = max(st[p], st[p ^ 1]);
    }
    ll query(ll l, ll r)
    {
        ll ans = -1e10;
        for (l += n - 1, r += n; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                ans = max(ans, st[l++]);
            if (r & 1)
                ans = max(ans, st[--r]);
        }
        return ans;
    }
};
const ll N = 1e5 + 5;
array<ll, 3> a[N];
SegTree st[4];
ll relax(ll l, ll r)
{
    if ((r - l) & 1) return 0;
    return max(st[l & 1].query(l, r), st[((l + 1) & 1) + 2].query(l, r));
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
    ll n = W.size(), q = E.size();
    for (ll i = 1; i <= n; i++)
        a[i] = {W[i - 1], A[i - 1], B[i - 1]};
    sort(a + 1, a + n + 1);
    pair<ll, ll> qs[q];
    for (ll i = 0; i < q; i++)
        qs[i] = make_pair(E[i], i);
    sort(qs, qs + q);
    pair<ll, ll> diff[n - 1];
    for (ll i = 0; i < n - 1; i++)
        diff[i] = make_pair(a[i + 2][0] - a[i + 1][0], i + 1);
    sort(diff, diff + n - 1);
    ll ptr = 0, lef[n + 1], rig[n + 1], res = 0;
    for (ll i = 1; i <= n; i++)
        res += a[i][1];
    for (ll i = 1; i <= n; i++)
        lef[i] = rig[i] = i;
    st[0] = st[1] = st[2] = st[3] = SegTree(n);
    for (ll i = 1; i <= n; i++) st[i & 1].set(i, a[i][2] - a[i][1]);
    st[0].build();
    st[1].build();
    vector<ll> ans(q);
    if (n == 1)
    {
        for (ll i = 0; i < q; i++) ans[i] = a[1][1];
        return ans;
    }
    pair<ll, ll> diff1[n - 2];
    for (ll i = 2; i < n; i++)
        diff1[i - 2] = make_pair(a[i + 1][0] - a[i - 1][0], i);
    sort(diff1, diff1 + n - 2);
    ll ptr1 = 0;
    set<pair<ll, ll>> s;
    for (ll i = 1; i <= n; i++) s.insert(make_pair(i, i));
    for (auto [d, ind] : qs)
    {
        while (ptr < n - 1 and diff[ptr].first <= d)
        {
            ll i = diff[ptr].second;
            res += relax(lef[i], i) + relax(i + 1, rig[i + 1]);
            s.erase(make_pair(lef[i], i));
            s.erase(make_pair(i + 1, rig[i + 1]));
            rig[lef[i]] = rig[i + 1];
            lef[rig[i + 1]] = lef[i];
            res -= relax(lef[i], rig[i + 1]);
            s.insert(make_pair(lef[i], rig[i + 1]));
            ptr++;
        }
        while (ptr1 < n - 2 and diff1[ptr1].first <= d)
        {
            ll i = diff1[ptr1].second;
            auto [l, r] = *--s.upper_bound(make_pair(i, 1e9));
            res += relax(l, r);
            st[(i & 1) + 2].modify(i, a[i][2] - a[i][1]);
            res -= relax(l, r);
            ptr1++;
        }
        ans[ind] = res;
    }
    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: 15 / 15
• Subtask 7: 18 / 18