oj.uz

Submission #567908

# Submission time Handle Problem Language Result Execution time Memory
567908 2022-05-24T10:26:16 Z MilosMilutinovic Road Construction (JOI21_road_construction) C++14
100 / 100
 2909 ms 541484 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) 1e11;
  
int root_u[MAX], root_d[MAX], tsz, ls[30 * MAX], rs[30 * MAX], rootU, rootD;
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> 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);
  int sz = 1;
  while (sz < ys.size()) {
    sz <<= 1;
  }
  build(rootU, 0, sz - 1);
  build(rootD, 0, sz - 1);
  int prv_u = rootU;
  int prv_d = rootD;
  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, sz - 1, j, x[i] + y[i]);
    modify(root_d[i], prv_d, 0, sz - 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, sz - 1, 0, j - 1);
      if (val.first != -inf) {
        st.insert(make_tuple(x[i] + y[i] - val.first, i, val.second, 0));
      }
    }
    {
      auto val = query(root_d[i], 0, sz - 1, j + 1, sz - 1);
      if (val.first != -inf) {
        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, sz - 1, p, -inf);
      int j = GetId(i);
      auto val = query(root_u[i], 0, sz - 1, 0, j - 1);
      if (val.first != -inf) {
        st.insert(make_tuple(x[i] + y[i] - val.first, i, val.second, 0));
      }
    } else {
      modify(root_d[i], root_d[i], 0, sz - 1, p, -inf);
      int j = GetId(i);
      auto val = query(root_d[i], 0, sz - 1, j + 1, ys.size() - 1);
      if (val.first != -inf) {
        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;
      |             ~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:87:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   while (sz < ys.size()) {
      |          ~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 89972 KB Output is correct
2 Correct 368 ms 90096 KB Output is correct
3 Correct 345 ms 89712 KB Output is correct
4 Correct 332 ms 89764 KB Output is correct
5 Correct 416 ms 88960 KB Output is correct
6 Correct 4 ms 2016 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1809 ms 515996 KB Output is correct
2 Correct 1810 ms 515960 KB Output is correct
3 Correct 209 ms 89516 KB Output is correct
4 Correct 1218 ms 515672 KB Output is correct
5 Correct 1274 ms 515788 KB Output is correct
6 Correct 1316 ms 515744 KB Output is correct
7 Correct 1244 ms 515208 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1811 ms 385472 KB Output is correct
2 Correct 1841 ms 385516 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 832 ms 368688 KB Output is correct
5 Correct 1102 ms 390716 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1811 ms 385472 KB Output is correct
2 Correct 1841 ms 385516 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 832 ms 368688 KB Output is correct
5 Correct 1102 ms 390716 KB Output is correct
6 Correct 1899 ms 390420 KB Output is correct
7 Correct 1906 ms 390512 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1973 ms 390532 KB Output is correct
11 Correct 833 ms 368816 KB Output is correct
12 Correct 1081 ms 390760 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 89972 KB Output is correct
2 Correct 368 ms 90096 KB Output is correct
3 Correct 345 ms 89712 KB Output is correct
4 Correct 332 ms 89764 KB Output is correct
5 Correct 416 ms 88960 KB Output is correct
6 Correct 4 ms 2016 KB Output is correct
7 Correct 1496 ms 296464 KB Output is correct
8 Correct 1489 ms 296628 KB Output is correct
9 Correct 303 ms 89788 KB Output is correct
10 Correct 1120 ms 295580 KB Output is correct
11 Correct 1344 ms 295716 KB Output is correct
12 Correct 890 ms 296304 KB Output is correct
13 Correct 920 ms 294836 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 89972 KB Output is correct
2 Correct 368 ms 90096 KB Output is correct
3 Correct 345 ms 89712 KB Output is correct
4 Correct 332 ms 89764 KB Output is correct
5 Correct 416 ms 88960 KB Output is correct
6 Correct 4 ms 2016 KB Output is correct
7 Correct 1809 ms 515996 KB Output is correct
8 Correct 1810 ms 515960 KB Output is correct
9 Correct 209 ms 89516 KB Output is correct
10 Correct 1218 ms 515672 KB Output is correct
11 Correct 1274 ms 515788 KB Output is correct
12 Correct 1316 ms 515744 KB Output is correct
13 Correct 1244 ms 515208 KB Output is correct
14 Correct 1811 ms 385472 KB Output is correct
15 Correct 1841 ms 385516 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 832 ms 368688 KB Output is correct
18 Correct 1102 ms 390716 KB Output is correct
19 Correct 1899 ms 390420 KB Output is correct
20 Correct 1906 ms 390512 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1973 ms 390532 KB Output is correct
24 Correct 833 ms 368816 KB Output is correct
25 Correct 1081 ms 390760 KB Output is correct
26 Correct 1496 ms 296464 KB Output is correct
27 Correct 1489 ms 296628 KB Output is correct
28 Correct 303 ms 89788 KB Output is correct
29 Correct 1120 ms 295580 KB Output is correct
30 Correct 1344 ms 295716 KB Output is correct
31 Correct 890 ms 296304 KB Output is correct
32 Correct 920 ms 294836 KB Output is correct
33 Correct 2909 ms 541312 KB Output is correct
34 Correct 2898 ms 541484 KB Output is correct
35 Correct 2299 ms 540428 KB Output is correct
36 Correct 1585 ms 541304 KB Output is correct
37 Correct 1675 ms 541140 KB Output is correct
38 Correct 1662 ms 539860 KB Output is correct