oj.uz

Submission #543196

# Submission time Handle Problem Language Result Execution time Memory
543196 2022-03-29T18:31:01 Z erray Road Construction (JOI21_road_construction) C++17
100 / 100
 9117 ms 33308 KB 
// author: erray
#include <bits/stdc++.h>

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

using namespace std;



const long long inf = (long long) 1e10;
using T = pair<long long, int>;
struct SegTree {
  vector<T> tree;
  int n;
  SegTree(int _n) : n(_n) {
    tree.resize(n << 1, pair{-inf, -1});
  }  

  T get(int l, int r) {
    T 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, long long 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<long long>> pqs(s);
      for (int i = 0; i < N; ++i) {
        auto[cx, cy] = A[i];
        int cs = c[i];
        vector<pair<int, long long>> 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});
          long long nw = (pqs[ind].empty() ? -inf : (long long) 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1405 ms 7096 KB Output is correct
2 Correct 1455 ms 7188 KB Output is correct
3 Correct 1388 ms 7112 KB Output is correct
4 Correct 1073 ms 7248 KB Output is correct
5 Correct 1340 ms 6088 KB Output is correct
6 Correct 11 ms 408 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1622 ms 13140 KB Output is correct
2 Correct 1578 ms 11656 KB Output is correct
3 Correct 611 ms 6900 KB Output is correct
4 Correct 1387 ms 11316 KB Output is correct
5 Correct 1448 ms 11568 KB Output is correct
6 Correct 1444 ms 11712 KB Output is correct
7 Correct 1435 ms 12904 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3830 ms 27712 KB Output is correct
2 Correct 4368 ms 27716 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 592 ms 8764 KB Output is correct
5 Correct 667 ms 6844 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3830 ms 27712 KB Output is correct
2 Correct 4368 ms 27716 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 592 ms 8764 KB Output is correct
5 Correct 667 ms 6844 KB Output is correct
6 Correct 4617 ms 28240 KB Output is correct
7 Correct 4418 ms 28180 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 4265 ms 25664 KB Output is correct
11 Correct 586 ms 9028 KB Output is correct
12 Correct 693 ms 6976 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1405 ms 7096 KB Output is correct
2 Correct 1455 ms 7188 KB Output is correct
3 Correct 1388 ms 7112 KB Output is correct
4 Correct 1073 ms 7248 KB Output is correct
5 Correct 1340 ms 6088 KB Output is correct
6 Correct 11 ms 408 KB Output is correct
7 Correct 4525 ms 16772 KB Output is correct
8 Correct 4590 ms 16688 KB Output is correct
9 Correct 1101 ms 7228 KB Output is correct
10 Correct 3288 ms 14988 KB Output is correct
11 Correct 2620 ms 14392 KB Output is correct
12 Correct 1238 ms 8724 KB Output is correct
13 Correct 1928 ms 7348 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1405 ms 7096 KB Output is correct
2 Correct 1455 ms 7188 KB Output is correct
3 Correct 1388 ms 7112 KB Output is correct
4 Correct 1073 ms 7248 KB Output is correct
5 Correct 1340 ms 6088 KB Output is correct
6 Correct 11 ms 408 KB Output is correct
7 Correct 1622 ms 13140 KB Output is correct
8 Correct 1578 ms 11656 KB Output is correct
9 Correct 611 ms 6900 KB Output is correct
10 Correct 1387 ms 11316 KB Output is correct
11 Correct 1448 ms 11568 KB Output is correct
12 Correct 1444 ms 11712 KB Output is correct
13 Correct 1435 ms 12904 KB Output is correct
14 Correct 3830 ms 27712 KB Output is correct
15 Correct 4368 ms 27716 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 592 ms 8764 KB Output is correct
18 Correct 667 ms 6844 KB Output is correct
19 Correct 4617 ms 28240 KB Output is correct
20 Correct 4418 ms 28180 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 4265 ms 25664 KB Output is correct
24 Correct 586 ms 9028 KB Output is correct
25 Correct 693 ms 6976 KB Output is correct
26 Correct 4525 ms 16772 KB Output is correct
27 Correct 4590 ms 16688 KB Output is correct
28 Correct 1101 ms 7228 KB Output is correct
29 Correct 3288 ms 14988 KB Output is correct
30 Correct 2620 ms 14392 KB Output is correct
31 Correct 1238 ms 8724 KB Output is correct
32 Correct 1928 ms 7348 KB Output is correct
33 Correct 9037 ms 32984 KB Output is correct
34 Correct 9117 ms 33308 KB Output is correct
35 Correct 6940 ms 25728 KB Output is correct
36 Correct 1891 ms 10852 KB Output is correct
37 Correct 1958 ms 11200 KB Output is correct
38 Correct 2351 ms 10764 KB Output is correct