Submission #543195

#	Time	Username	Problem	Language	Result	Execution time	Memory
543195		erray	Road Construction (JOI21_road_construction)	C++14	Compilation error	0 ms	0 KiB

road_construction

// 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';
  }
}

Compilation message (stderr)

road_construction.cpp: In constructor 'SegTree::SegTree(int)':
road_construction.cpp:20:29: error: missing template arguments before '{' token
   20 |     tree.resize(n << 1, pair{-inf, -1});
      |                             ^
road_construction.cpp: In lambda function:
road_construction.cpp:77:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |         auto[cx, cy] = A[i];
      |             ^
road_construction.cpp:83:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |           auto[x, ind] = st.get(0, max(0, g));
      |               ^
road_construction.cpp:99:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |         for (auto[x, b] : rb) {
      |                  ^