Submission #969205

#	Time	Username	Problem	Language	Result	Execution time	Memory
969205		abczz	Road Construction (JOI21_road_construction)	C++14	0 / 100	10055 ms	311772 KiB

road_construction

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

struct SegTree{
  ll cnt = 0;
  struct Node{
    vector <ll> V;
    ll chl = -1;
    ll chr = -1;
  };
  vector <Node> st;
  void get(ll &id) {
    if (id == -1) {
      st.push_back({{}, -1, -1});
      id = ++cnt;
    }
  }
  void add(ll &id, ll l, ll r, ll x, ll y) {
    get(id);
    if (l == r) {
      st[id].V.push_back(y);
      return;
    }
    ll mid = (l+r)/2;
    if (x <= mid) {
      ll tmp = st[id].chl;
      add(tmp, l, mid, x, y);
      st[id].chl = tmp;
    }
    else {
      ll tmp = st[id].chr;
      add(tmp, mid+1, r, x, y);
      st[id].chr = tmp;
    }
  }
  void build(ll id, ll l, ll r) {
    if (st[id].chl == -1 && st[id].chr == -1) {
      sort(st[id].V.begin(), st[id].V.end());
      return;
    }
    ll mid = (l+r)/2;
    if (st[id].chr == -1) {
      build(st[id].chl, l, mid);
      st[id].V = st[st[id].chl].V;
    }
    else if (st[id].chl == -1) {
      build(st[id].chr, mid+1, r);
      st[id].V = st[st[id].chr].V;
    }
    else {
      build(st[id].chl, l, mid);
      build(st[id].chr, mid+1, r);
      int i = 0, j = 0;
      while (i < st[st[id].chl].V.size() && j < st[st[id].chr].V.size()) {
        if (st[st[id].chl].V[i] <= st[st[id].chr].V[j]) st[id].V.push_back(st[st[id].chl].V[i++]);
        else st[id].V.push_back(st[st[id].chr].V[j++]);
      }
      while (i < st[st[id].chl].V.size()) st[id].V.push_back(st[st[id].chl].V[i++]);
      while (j < st[st[id].chr].V.size()) st[id].V.push_back(st[st[id].chr].V[j++]);
    }
  }
  ll query(ll id, ll l, ll r, ll xl, ll xr, ll yl, ll yr) {
    if (id == -1 || xr < l || r < xl) return 0;
    else if (xl <= l && r <= xr) {
      auto itL = lower_bound(st[id].V.begin(), st[id].V.end(), yl);
      auto itR = lower_bound(st[id].V.begin(), st[id].V.end(), yr+1);
      return itR-itL;
    }
    ll mid = (l+r)/2;
    return query(st[id].chl, l, mid, xl, xr, yl, yr) + query(st[id].chr, mid+1, r, xl, xr, yl, yr);
  }
}ST;

ll n, f, k, x, l = 0, rt, r = 4e9, mid;
array <ll, 2> A[250000];
void solve(ll u) {
  f = 0;
  for (int i=0; i<n; ++i) {
    f += ST.query(rt, 0LL, (ll)4e9, max(0LL, A[i][0]+A[i][1]-u), min((ll)4e9, A[i][0]+A[i][1]+u), A[i][0]-A[i][1]-u, A[i][0]-A[i][1]+u);
  }
  f -= n;
  f /= 2;
}

void dnc(ll l, ll r, ll ql, ll qr) {
  if (l == r) {
    for (int i=ql; i<=qr; ++i) cout << l << '\n';
    return;
  }
  ll mid = (l+r)/2;
  solve(mid);
  ll tmp = f;
  if (tmp && tmp != ql) dnc(l, mid, ql, tmp);
  if (tmp < qr) dnc(mid+1, r, tmp, qr);
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  ST.st.push_back({{}, -1, -1});
  cin >> n >> k;
  for (int i=0; i<n; ++i) {
    cin >> A[i][0] >> A[i][1];
    A[i][0] += (ll)1e9, A[i][1] += (ll)1e9;
    ST.add(rt, 0LL, (ll)4e9, A[i][0]+A[i][1], A[i][0]-A[i][1]);
  }
  ST.build(rt, 0LL, (ll)4e9);
  dnc(0, (ll)4e9, 1, k);
}

Compilation message (stderr)

road_construction.cpp: In member function 'void SegTree::build(long long int, long long int, long long int)':
road_construction.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |       while (i < st[st[id].chl].V.size() && j < st[st[id].chr].V.size()) {
      |              ~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:59:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |       while (i < st[st[id].chl].V.size() && j < st[st[id].chr].V.size()) {
      |                                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |       while (i < st[st[id].chl].V.size()) st[id].V.push_back(st[st[id].chl].V[i++]);
      |              ~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |       while (j < st[st[id].chr].V.size()) st[id].V.push_back(st[st[id].chr].V[j++]);
      |              ~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35