oj.uz

Submission #567823

# Submission time Handle Problem Language Result Execution time Memory
567823 2022-05-24T08:48:16 Z MilosMilutinovic Road Construction (JOI21_road_construction) C++14
6 / 100
 2306 ms 519108 KB 
/**
 *    author:  wxhtzdy
 *    created: 24.05.2022 08:24:38
**/
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAX = 2000000;
const int inf = (int) 5e9;
  
int root_u[MAX], root_d[MAX], tsz, ls[30 * MAX], rs[30 * MAX], root;
pair<int, int> mx[30 * MAX];

void build(int& node, int l, int r) {
  node = ++tsz;
  mx[node] = make_pair(-inf, l);
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  build(ls[node], l, mid);
  build(rs[node], mid + 1, r);
}

void modify(int& node, int pnode, int l, int r, int i, int v) {
  node = ++tsz;
  ls[node] = ls[pnode];
  rs[node] = rs[pnode];
  if (l == r) {
    mx[node] = make_pair(v, l);
    return;
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    modify(ls[node], ls[pnode], l, mid, i, v);
  } else {
    modify(rs[node], rs[pnode], mid + 1, r, i, v);
  }
  mx[node] = max(mx[ls[node]], mx[rs[node]]);
}

pair<int, int> query(int node, int l, int r, int ll, int rr) {
  if (l > r || l > rr || r < ll || ll > rr) {
    return make_pair(-inf, l);
  }
  if (ll <= l && r <= rr) {
    return mx[node];
  }
  int mid = l + r >> 1;
  return max(query(ls[node], l, mid, ll, rr), query(rs[node], mid + 1, r, ll, rr));
}

signed 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];
  }
  vector<int> xs;
  for (int i = 0; i < n; i++) {
    xs.push_back(x[i]);
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    if (x[i] != x[j]) {
      return x[i] < x[j];
    } else {
      return y[i] < y[j];
    }
  });         
  vector<int> idx(n);
  for (int i = 0; i < n; i++) {
    idx[order[i]] = i;
  }
  vector<pair<int, int>> ys;
  for (int i : order) {
    ys.emplace_back(y[i], x[i]);
  }
  sort(ys.begin(), ys.end());
  ys.erase(unique(ys.begin(), ys.end()), ys.end());
  mx[0] = make_pair(-inf, 0);
  build(root, 0, ys.size() - 1);
  int prv_u = root;
  int prv_d = root;
  auto GetId = [&](int i) {
    return lower_bound(ys.begin(), ys.end(), make_pair(y[i], x[i])) - ys.begin();
  };
  for (int i : order) {
    int j = GetId(i);
    modify(root_u[i], prv_u, 0, ys.size() - 1, j, x[i] + y[i]);
    modify(root_d[i], prv_d, 0, ys.size() - 1, j, x[i] - y[i]);
    prv_u = root_u[i];
    prv_d = root_d[i];
  }
  set<tuple<int, int, int, int>> st;
  for (int i = 0; i < n; i++) {
    int j = GetId(i);
    {
      auto val = query(root_u[i], 0, ys.size() - 1, 0, j - 1);
      st.insert(make_tuple(x[i] + y[i] - val.first, i, val.second, 0));
    }
    {
      auto val = query(root_d[i], 0, ys.size() - 1, j + 1, ys.size() - 1);
      st.insert(make_tuple(x[i] - y[i] - val.first, i, val.second, 1));
    }
  }
  for (int b = 0; b < k; b++) {
    auto it = st.begin();
    cout << get<0>(*it) << '\n';
    int i = get<1>(*it);
    int p = get<2>(*it);
    int d = get<3>(*it);
    st.erase(it);
    if (d == 0) {
      modify(root_u[i], root_u[i], 0, ys.size() - 1, p, -inf);
      int j = GetId(i);
      auto val = query(root_u[i], 0, ys.size() - 1, 0, j - 1);
      st.insert(make_tuple(x[i] + y[i] - val.first, i, val.second, 0));
    } else {
      modify(root_d[i], root_d[i], 0, ys.size() - 1, p, -inf);
      int j = GetId(i);
      auto val = query(root_d[i], 0, ys.size() - 1, j + 1, ys.size() - 1);
      st.insert(make_tuple(x[i] - y[i] - val.first, i, val.second, 1));
    }
  }                 
  return 0;
}

Compilation message

road_construction.cpp: In function 'void build(long long int&, long long int, long long int)':
road_construction.cpp:23:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int mid = l + r >> 1;
      |             ~~^~~
road_construction.cpp: In function 'void modify(long long int&, long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid = l + r >> 1;
      |             ~~^~~
road_construction.cpp: In function 'std::pair<long long int, long long int> query(long long int, long long int, long long int, long long int, long long int)':
road_construction.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 89784 KB Output is correct
2 Correct 327 ms 89804 KB Output is correct
3 Incorrect 347 ms 86180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2237 ms 519108 KB Output is correct
2 Correct 2306 ms 519084 KB Output is correct
3 Correct 224 ms 86048 KB Output is correct
4 Correct 1591 ms 518744 KB Output is correct
5 Correct 1860 ms 518976 KB Output is correct
6 Correct 1827 ms 519052 KB Output is correct
7 Correct 1762 ms 518336 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1967 ms 369544 KB Output is correct
2 Correct 2027 ms 369416 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1967 ms 369544 KB Output is correct
2 Correct 2027 ms 369416 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 89784 KB Output is correct
2 Correct 327 ms 89804 KB Output is correct
3 Incorrect 347 ms 86180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 89784 KB Output is correct
2 Correct 327 ms 89804 KB Output is correct
3 Incorrect 347 ms 86180 KB Output isn't correct
4 Halted 0 ms 0 KB -