Submission #1176230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176230		avighna	Nile (IOI24_nile)	C++20	100 / 100	144 ms	26040 KiB

nile

#include "nile.h"
#include <algorithm>
#include <functional>
#include <numeric>
#include <set>

typedef long long ll;

struct Item {
  ll w, del;
};

struct Query {
  ll e, i;
};

std::vector<ll> calculate_costs(std::vector<int> W, std::vector<int> A,
                                std::vector<int> B, std::vector<int> E) {
  const ll n = W.size();
  std::vector<Item> items(n);
  ll sum_a = 0;
  for (ll i = 0; i < n; ++i) {
    items[i] = {W[i], A[i] - B[i]};
    sum_a += A[i];
  }
  std::sort(items.begin(), items.end(),
            [](Item a, Item b) { return a.w < b.w; });

  std::vector<Query> queries;
  for (ll i = 0; i < E.size(); ++i) {
    queries.push_back({E[i], i});
  }
  std::sort(queries.begin(), queries.end(),
            [](Query a, Query b) { return a.e < b.e; });

  std::set<std::pair<ll, ll>> merge_ranges;
  for (ll i = 1; i < n; ++i) {
    merge_ranges.insert({items[i].w - items[i - 1].w, i});
  }
  std::set<std::pair<ll, ll>> add_elements;
  for (ll i = 1; i < n - 1; ++i) {
    add_elements.insert({items[i + 1].w - items[i - 1].w, i});
  }

  // the set of all odd/even positioned elements satisfying W[i+1] - W[i-1] <= e
  std::vector<ll> min_odd(n, 1e15), min_even(n, 1e15), odd(n, 1e15), even(n);
  std::vector<ll> par(n), sz(n, 1), contrib(n), tot(n);
  std::iota(par.begin(), par.end(), 0LL);
  ll cur = 0;
  for (ll i = 0; i < n; ++i) {
    even[i] = tot[i] = items[i].del;
  }

  std::function<ll(ll)> root;
  root = [&](ll x) { return x == par[x] ? x : par[x] = root(par[x]); };

  std::function<void(ll)> update;
  auto merge = [&](ll x, ll y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      return;
    }
    if (x > y) {
      std::swap(x, y);
    }
    if (sz[x] % 2 == 0) {
      min_odd[x] = std::min(min_odd[x], min_odd[y]);
      min_even[x] = std::min(min_even[x], min_even[y]);
      odd[x] = std::min(odd[x], odd[y]);
      even[x] = std::min(even[x], even[y]);
    } else {
      min_odd[x] = std::min(min_odd[x], min_even[y]);
      min_even[x] = std::min(min_even[x], min_odd[y]);
      odd[x] = std::min(odd[x], even[y]);
      even[x] = std::min(even[x], odd[y]);
    }
    sz[x] += sz[y], sz[y] = 0;
    tot[x] += tot[y], tot[y] = 0;
    par[y] = x;
    cur -= contrib[x] + contrib[y], contrib[x] = contrib[y] = 0;
    update(x);
  };

  update = [&](ll x) {
    contrib[x] = tot[x];
    if (sz[x] % 2 == 1) {
      contrib[x] -= std::min(
          {items[x].del, items[x + sz[x] - 1].del, min_odd[x], even[x]});
    }
    cur += contrib[x];
  };

  std::vector<ll> answers(E.size());
  for (auto &[e, i] : queries) {
    while (!add_elements.empty() and add_elements.begin()->first <= e) {
      auto i = add_elements.begin()->second;
      auto r = root(i);
      if ((i - r) % 2 == 0) {
        min_even[r] = std::min(min_even[r], items[i].del);
      } else {
        min_odd[r] = std::min(min_odd[r], items[i].del);
      }
      cur -= contrib[r];
      update(r);
      add_elements.erase(add_elements.begin());
    }
    while (!merge_ranges.empty() and merge_ranges.begin()->first <= e) {
      auto i = merge_ranges.begin()->second;
      merge(i, i - 1);
      merge_ranges.erase(merge_ranges.begin());
    }
    answers[i] = sum_a - cur;
  }

  return answers;
}

• 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