Submission #554754

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
554754	2022-04-29T11:05:20 Z	MilosMilutinovic	Road Construction (JOI21_road_construction)	C++14	Compilation error	0 ms	0 KB

road_construction

#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> x(n);
  vector<int> y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }
  auto Count = [&](long long d) {
    vector<tuple<long long, int, long long, long long>> ev;
    vector<long long> xs;
    for (int i = 0; i < n; i++) {
      long long dx = x[i] + y[i];
      long long dy = x[i] - y[i];
      ev.emplace_back(dx - d, 0, dy - d - 1, dy + d);
      ev.emplace_back(dx + d + 1, 1, dy - d - 1, dy + d);
      ev.emplace_back(dx, 2, dy, dy);
      xs.push_back(dy - d - 1);
      xs.push_back(dy + d);
      xs.push_back(dy);
    }
    sort(ev.begin(), ev.end());
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    int sz = xs.size();
    fenwick<int> fenw(sz);
    long long cnt = 0;
    for (auto& e : ev) {
      int t = get<1>(e);
      if (t == 0) {
        int L = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
        int R = lower_bound(xs.begin(), xs.end(), get<3>(e)) - xs.begin();
        cnt -= fenw.get(R) - fenw.get(L);
      } else if (t == 1) {
        int L = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
        int R = lower_bound(xs.begin(), xs.end(), get<3>(e)) - xs.begin();
        cnt += fenw.get(R) - fenw.get(L);
      } else {
        int aa = lower_bound(xs.begin(), xs.end(), get<2>(e)) - xs.begin();
        fenw.modify(aa, +1);
      }
    }
    if (d == 4) {
      cout << cnt << '\n';
    }
    return (cnt - n) / 2;
  };
  long long low = 0, high = 4.1e9;
  while (low + 1 < high) {
    long long mid = (low + high + 1) >> 1;
    if (Count(mid) >= k) {
      high = mid;
    } else {
      low = mid;
    }
  }
  cout << high << '\n';
  return 0;
}

Compilation message

road_construction.cpp:45:2: error: extended character   is not valid in an identifier
   45 |       ev.emplace_back(dx - d, 0, dy - d - 1, dy + d);
      |  ^
road_construction.cpp:45:5: error: extended character   is not valid in an identifier
   45 |       ev.emplace_back(dx - d, 0, dy - d - 1, dy + d);
      |    ^
road_construction.cpp:45:8: error: extended character   is not valid in an identifier
   45 |       ev.emplace_back(dx - d, 0, dy - d - 1, dy + d);
      |      ^
road_construction.cpp:46:2: error: extended character   is not valid in an identifier
   46 |       ev.emplace_back(dx + d + 1, 1, dy - d - 1, dy + d);
      |  ^
road_construction.cpp:46:5: error: extended character   is not valid in an identifier
   46 |       ev.emplace_back(dx + d + 1, 1, dy - d - 1, dy + d);
      |    ^
road_construction.cpp:46:8: error: extended character   is not valid in an identifier
   46 |       ev.emplace_back(dx + d + 1, 1, dy - d - 1, dy + d);
      |      ^
road_construction.cpp:48:2: error: extended character   is not valid in an identifier
   48 |       xs.push_back(dy - d - 1);
      |  ^
road_construction.cpp:48:5: error: extended character   is not valid in an identifier
   48 |       xs.push_back(dy - d - 1);
      |    ^
road_construction.cpp:48:8: error: extended character   is not valid in an identifier
   48 |       xs.push_back(dy - d - 1);
      |      ^
road_construction.cpp: In lambda function:
road_construction.cpp:45:2: error: '\U000000a0' was not declared in this scope
   45 |       ev.emplace_back(dx - d, 0, dy - d - 1, dy + d);
      |  ^
road_construction.cpp:46:4: error: expected ';' before '\U000000a0'
   46 |       ev.emplace_back(dx + d + 1, 1, dy - d - 1, dy + d);
      |   ^~
      |   ;
road_construction.cpp:48:4: error: expected ';' before '\U000000a0'
   48 |       xs.push_back(dy - d - 1);
      |   ^~
      |   ;