oj.uz

Submission #969180

# Submission time Handle Problem Language Result Execution time Memory
969180 2024-04-24T16:11:36 Z abczz Road Construction (JOI21_road_construction) C++14
0 / 100
 10000 ms 313332 KB 
#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;
}
int main() {
  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);
  while (true) {
    while (l < r) {
      mid = (l+r)/2;
      solve(mid);
      if (f > x) r = mid;
      else l = mid+1;
    }
    solve(l);
    while (x < min(f, k)) {
      cout << l << '\n';
      ++x;
    }
    if (x == k) break;
    ++l;
    r = 4e9;
  }
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Execution timed out 10042 ms 2248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10080 ms 299088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10019 ms 313332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10019 ms 313332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10042 ms 2248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10042 ms 2248 KB Time limit exceeded
2 Halted 0 ms 0 KB -