Submission #1013585

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1013585	2024-07-03T16:48:22 Z	spacewalker	Ideal city (IOI12_city)	C++17	100 / 100	29 ms	13908 KB

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

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.0 / 11.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	440 KB	Output is correct
11	Correct	348 KB	Output is correct

Subtask #2
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	444 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct

Subtask #3
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	1484 KB	Output is correct
2	Correct	4 ms	1624 KB	Output is correct
3	Correct	10 ms	3160 KB	Output is correct
4	Correct	10 ms	3420 KB	Output is correct
5	Correct	20 ms	5976 KB	Output is correct
6	Correct	19 ms	6324 KB	Output is correct
7	Correct	20 ms	6448 KB	Output is correct
8	Correct	21 ms	5980 KB	Output is correct
9	Correct	21 ms	6584 KB	Output is correct
10	Correct	27 ms	13908 KB	Output is correct

Subtask #4
45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2136 KB	Output is correct
2	Correct	5 ms	2140 KB	Output is correct
3	Correct	14 ms	4952 KB	Output is correct
4	Correct	12 ms	4376 KB	Output is correct
5	Correct	26 ms	9412 KB	Output is correct
6	Correct	22 ms	7404 KB	Output is correct
7	Correct	29 ms	9752 KB	Output is correct
8	Correct	23 ms	7692 KB	Output is correct
9	Correct	22 ms	6940 KB	Output is correct
10	Correct	28 ms	6768 KB	Output is correct

Submission #1013585

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 21.0 / 21.0

Subtask #3 23.0 / 23.0

Subtask #4 45.0 / 45.0

Subtask #1
11.0 / 11.0

Subtask #2
21.0 / 21.0

Subtask #3
23.0 / 23.0

Subtask #4
45.0 / 45.0