Submission #1105027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105027		flashmt	Nile (IOI24_nile)	C++17	100 / 100	268 ms	35900 KiB

nile

#include <bits/stdc++.h>
using namespace std;
const int oo = 1 << 30;

template<typename T>
struct SegmentTree
{
  int low, mid, high;
  T value;
  SegmentTree *l, *r;

  SegmentTree(int low, int high, vector<T> &initial): low(low), high(high)
  {
    mid = (low + high) / 2;
    if (low == high)
    {
      l = r = NULL;
      value = initial[low];
    }
    else
    {
      l = new SegmentTree(low, mid, initial);
      r = new SegmentTree(mid + 1, high, initial);
      value = min(l->value, r->value);
    }
  }

  void update(int x, T v)
  {
    if (low == high)
    {
      value = v;
      return;
    }
    if (x <= mid) l->update(x, v);
    else r->update(x, v);
    value = min(l->value, r->value);
  }

  T get(int x, int y)
  {
    if (low == x && high == y)
      return value;
    if (y <= mid) return l->get(x, y);
    else if (x > mid) return r->get(x, y);
    else return min(l->get(x, mid), r->get(mid + 1, y));
  }
};

vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e)
{
  int n = size(w);
  long long curAns = accumulate(begin(a), end(a), 0LL);
  vector<pair<int, int>> c;
  for (int i = 0; i < n; i++)
    c.push_back({w[i], a[i] - b[i]});
  sort(begin(c), end(c));
  vector<pair<int, int>> diffs;
  for (int i = 0; i < n - 1; i++)
  {
    diffs.push_back({c[i + 1].first - c[i].first, i});
    if (i < n - 2)
      diffs.push_back({c[i + 2].first - c[i].first, i + n - 1});
  }
  sort(begin(diffs), end(diffs));
  set<int> active;
  for (int i = -1; i < n; i++)
    active.insert(i);

  vector<int> odd, even;
  for (int i = 0; i < n; i++)
    if (i % 2)
    {
      odd.push_back(c[i].second);
      even.push_back(oo);
    }
    else
    {
      odd.push_back(oo);
      even.push_back(c[i].second);
    }

  SegmentTree<int> oddTree(0, n - 1, odd);
  SegmentTree<int> evenTree(0, n - 1, even);

  map<int, long long> ansMap;
  ansMap[-1] = curAns;

  auto getScore = [&](int i)
  {
    auto u = active.lower_bound(i);
    int r = *u;
    u--;
    int l = *u + 1;
    int len = r - l + 1;
    if (len % 2 == 0)
      return 0;
    return l % 2 ? oddTree.get(l, r) : evenTree.get(l, r);
  };

  for (int i = 0; i < size(diffs);)
  {
    auto [curDiff, _] = diffs[i];
    int j = i;
    while (j < size(diffs))
    {
      auto [d, id] = diffs[j];
      if (d > curDiff)
        break;

      if (id < n - 1)
      {
        curAns -= getScore(id) + getScore(id + 1);
        active.erase(id);
        curAns += getScore(id);
      }
      else
      {
        id -= n - 1;
        curAns -= getScore(id);
        if (id % 2) oddTree.update(id + 1, c[id + 1].second);
        else evenTree.update(id + 1, c[id + 1].second);
        curAns += getScore(id);
      }

      j++;
    }

    i = j;
    ansMap[curDiff] = curAns;
  }

  vector<long long> ans;
  for (int d : e)
  {
    auto it = ansMap.upper_bound(d);
    it--;
    ans.push_back(it->second);
  }
  return ans;
}

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:101:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for (int i = 0; i < size(diffs);)
      |                   ~~^~~~~~~~~~~~~
nile.cpp:105:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     while (j < size(diffs))
      |            ~~^~~~~~~~~~~~~

• 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