Submission #1013585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013585		spacewalker	Ideal city (IOI12_city)	C++17	100 / 100	29 ms	13908 KiB

city

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
constexpr ll MOD = 1'000'000'000;

struct Segment {
  int x, y1, y2;
  Segment(int x, int y1, int y2) : x(x), y1(y1), y2(y2) {}
};

ostream& operator << (ostream& os, const Segment &s) {
  return os << "[x = " << s.x << "; y = " << s.y1 << "..." << s.y2 << "]";
}

bool adjacent(const Segment &a, const Segment &b) {
  return abs(a.x - b.x) <= 1 && max(a.y1, b.y1) <= min(a.y2, b.y2); 
}

vector<Segment> divide_into_segments(const vector<pair<int, int>> &blocks) {
  vector<Segment> segments;
  optional<Segment> currentSegment;
  for (int i = 0; i < blocks.size(); ++i) {
    if (!currentSegment) currentSegment = Segment(blocks[i].first, blocks[i].second, blocks[i].second);
    else if (currentSegment->x != blocks[i].first || currentSegment->y2 + 1 < blocks[i].second) {
      segments.push_back(*currentSegment);
      currentSegment = Segment(blocks[i].first, blocks[i].second, blocks[i].second);
    } else {
      currentSegment->y2 = blocks[i].second;
    }
  }
  if (currentSegment) segments.push_back(*currentSegment);
  return segments;
}

ll pair_distance_sum(const vector<ll> &points) {
  if (points.size() == 0) {
    return 0;
  }
  ll ans = 0;
  ll total = accumulate(points.begin(), points.end(), 0LL);
  ll right_side = 0;
  for (int i = 0; i < points.size(); ++i) {
    right_side += points[i];
    ans += right_side * (total - right_side) % MOD;
  }
  /*
  cerr << "PDS " << ans;
  for (ll v : points) cerr << " " << v;
  cerr << endl;
  */
  return ans % MOD;
}

vector<vector<ll>> segments_reachable;

ll sum_of_distances(int n, const vector<vector<int>> &tree, const vector<Segment> &segs, int v, int p) {
  auto cseg = segs[v];
  int length = cseg.y2 - cseg.y1 + 1;
  segments_reachable[v].assign(length, 1);

  auto comp = [&] (int y) {
    return clamp(y, cseg.y1, cseg.y2) - cseg.y1;
  };

  ll ans = 0;
  for (int child : tree[v]) {
    if (child == p) continue;
    ans += sum_of_distances(n, tree, segs, child, v);
    int comp_min = comp(segs[child].y1), comp_max = comp(segs[child].y2);
    vector<ll> csubsegment(comp_max - comp_min + 1); 
    ll segments_in_child = accumulate(segments_reachable[child].begin(),
        segments_reachable[child].end(), 0LL);
    for (int y = segs[child].y1; y <= segs[child].y2; ++y) {
      ll segments_here = segments_reachable[child][y - segs[child].y1];
      segments_reachable[v][comp(y)] += segments_here;
      csubsegment[comp(y) - comp_min] += segments_here;

      ll delta_y = abs(y - clamp(y, cseg.y1, cseg.y2)) + 1;
      ans += delta_y * segments_here % MOD * (n - segments_in_child) % MOD;
    }
    ans -= pair_distance_sum(csubsegment);
  }
  ans += pair_distance_sum(segments_reachable[v]);
  ans = (ans % MOD + MOD) % MOD;
  // cerr << "SOD " << v << " (par " << p << " " << segs[v] << ") ans " << ans << endl;
  return ans;
}


int DistanceSum(int N, int *X, int *Y) {
  segments_reachable.assign(N, vector<ll>());
  vector<pair<int, int>> blocks(N);
  for (int i = 0; i < N; ++i) blocks[i] = {X[i], Y[i]};
  sort(blocks.begin(), blocks.end());
  auto segments = divide_into_segments(blocks);

  // for (auto &s : segments) cerr << s << endl;

  int k = segments.size();
  vector<vector<int>> tree(k);

  for (int i = 0, j = 0, prev = 0; i < k; prev = i, i = j) {
    while (j < k && segments[j].x == segments[i].x) ++j;
    int cprev = prev;
    for (int cseg_i = i; cseg_i < j; ++cseg_i) {
      while (cprev < i && segments[cprev].y2 < segments[cseg_i].y1) ++cprev;
      while (cprev < i && adjacent(segments[cseg_i], segments[cprev])) {
        // cerr << "adjacent " << segments[cseg_i] << " " << segments[cprev] << endl;
        tree[cseg_i].push_back(cprev);
        tree[cprev].push_back(cseg_i);
        if (segments[cprev].y2 <= segments[cseg_i].y2) {
          ++cprev;
        } else {
          break;
        }
      }
    }
  }

  return sum_of_distances(N, tree, segments, 0, -1); 
}

Compilation message (stderr)

city.cpp: In function 'std::vector<Segment> divide_into_segments(const std::vector<std::pair<int, int> >&)':
city.cpp:24: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]
   24 |   for (int i = 0; i < blocks.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~~
city.cpp: In function 'll pair_distance_sum(const std::vector<long long int>&)':
city.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (int i = 0; i < points.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45