oj.uz

Submission #543191

# Submission time Handle Problem Language Result Execution time Memory
543191 2022-03-29T18:24:05 Z erray Road Construction (JOI21_road_construction) C++17
6 / 100
 4738 ms 24424 KB 
// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;



const int inf = int(2e9);
struct SegTree {
  vector<array<int, 2>> tree;
  int n;
  SegTree(int _n) : n(_n) {
    tree.resize(n << 1, array{-inf, -1});
  }  

  array<int, 2> get(int l, int r) {
    array<int, 2> res = {-inf, -1};
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) {
        res = max(res, tree[l++]); 
      }
      if (r & 1) {
        res = max(res, tree[--r]);
      }
    }
    return res;
  }

  void modify(int p, int x) {
    p += n;
    tree[p] = {x, p - n};
    while (p > 1) {
      tree[p >> 1] = max(tree[p], tree[p ^ 1]);
      p >>= 1;
    }
  }
};


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, K;
  cin >> N >> K;
  vector<array<int, 2>> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i][0] >> A[i][1];
  }
  sort(A.begin(), A.end());
  vector<int> ys(N);
  for (int i = 0; i < N; ++i) {
    ys[i] = A[i][1];
  }
  sort(ys.begin(), ys.end());
  ys.erase(unique(ys.begin(), ys.end()), ys.end());
  int s = int(ys.size());
  vector<int> c(N);
  for (int i = 0; i < N; ++i) {
    c[i] = int(lower_bound(ys.begin(), ys.end(), A[i][1]) - ys.begin()); 
  }


  auto Get = [&](long long lim) -> vector<long long> {
    debug(lim);
    vector<long long> res;
    bool reversed = false;
    auto Solve = [&] { 
      SegTree st(s);
      vector<priority_queue<int>> pqs(s);
      for (int i = 0; i < N; ++i) {
        auto[cx, cy] = A[i];
        int cs = c[i];
        vector<array<int, 2>> rb;
        int me = cx + cy;
        while (true) {
          int g = cs - reversed;
          auto[x, ind] = st.get(0, max(0, g));
          if (g < 0 || x == -inf || 0LL + me - x > lim) {
            break;
          }
          assert(pqs[ind].top() == x);
          pqs[ind].pop();
          res.push_back(0LL + me - x);
          if (int(res.size()) > K) {
            debug("end", lim);
            return;
          }
          rb.push_back({ind, x});
          int nw = (pqs[ind].empty() ? -inf : pqs[ind].top());
          st.modify(ind, nw);
        }

        for (auto[x, b] : rb) {
          pqs[x].push(b);
          st.modify(x, pqs[x].top());
        }
        pqs[cs].push(me);
        st.modify(cs, pqs[cs].top());
      }
    };

    auto Reverse = [&] {
      reversed ^= 1;
      for (int i = 0; i < N; ++i) {
        c[i] = s - 1 - c[i];
        A[i][1] = -A[i][1];
      }
    };
    Solve();
    Reverse();
    Solve();
    return res;
  };


  long long low = 0, high = (long long) 4e9;
  while (low < high) {
    long long mid = 1 + ((low + high) >> 1);
    debug(mid, Get(mid));
    if (int(Get(mid).size()) <= K) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  debug(low);

  auto ans = Get(low);
  sort(ans.begin(), ans.end());
  for (int i = 0; i < K; ++i) {
    cout << (i < int(ans.size()) ? ans[i] : low + 1) << '\n';
  }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1831 ms 6988 KB Output is correct
2 Correct 1817 ms 7032 KB Output is correct
3 Correct 1841 ms 7160 KB Output is correct
4 Incorrect 1446 ms 7052 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1732 ms 10688 KB Output is correct
2 Correct 1679 ms 10536 KB Output is correct
3 Correct 775 ms 6996 KB Output is correct
4 Correct 1548 ms 10748 KB Output is correct
5 Correct 1581 ms 11316 KB Output is correct
6 Correct 1597 ms 11524 KB Output is correct
7 Correct 1586 ms 9896 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3995 ms 24424 KB Output is correct
2 Correct 4738 ms 24312 KB Output is correct
3 Incorrect 1 ms 320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3995 ms 24424 KB Output is correct
2 Correct 4738 ms 24312 KB Output is correct
3 Incorrect 1 ms 320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1831 ms 6988 KB Output is correct
2 Correct 1817 ms 7032 KB Output is correct
3 Correct 1841 ms 7160 KB Output is correct
4 Incorrect 1446 ms 7052 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1831 ms 6988 KB Output is correct
2 Correct 1817 ms 7032 KB Output is correct
3 Correct 1841 ms 7160 KB Output is correct
4 Incorrect 1446 ms 7052 KB Output isn't correct
5 Halted 0 ms 0 KB -