Submission #1057353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057353		juicy	도로 건설 사업 (JOI13_construction)	C++17	100 / 100	350 ms	45088 KiB

construction

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n, m, c, p;
int lab[N], cands[N];
long long pf[N];
array<int, 3> pt[N];
array<int, 4> rect[N];
vector<array<int, 3>> edges;

int find(int u) {
  return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}

bool mrg(int u, int v) {
  if ((u = find(u)) == (v = find(v))) {
    return 0;
  }
  if (lab[u] > lab[v]) {
    swap(u, v);
  }
  lab[u] += lab[v];
  lab[v] = u;
  return 1;
}

void bld() {
  vector<array<int, 2>> events;
  for (int i = 1; i <= m; ++i) {
    events.push_back({rect[i][0], rect[i][3]});
    events.push_back({rect[i][2] + 1, -rect[i][3]});
  }
  multiset<int> st;
  auto add = [&](int x) {
    if (x > 0) {
      st.insert(x);
    } else {
      st.erase(st.find(-x));
    }
  };
  sort(pt + 1, pt + n + 1);
  sort(events.begin(), events.end());
  for (int i = 1, j = 0; i <= n; ++i) {
    while (j < 2 * m && events[j][0] <= pt[i][0]) {
      add(events[j++][1]);
    }
    int k = i;
    while (k + 1 <= n && pt[k + 1][0] == pt[i][0]) {
      ++k;
      auto it = st.lower_bound(pt[k - 1][1]);
      if (it != st.end() && *it < pt[k][1]) {
        continue;
      }
      edges.push_back({pt[k][1] - pt[k - 1][1], pt[k][2], pt[k - 1][2]});
    }
    i = k;
  }
}

long long qry(int b, int h) {
  if (h + p < n) {
    return -1;
  }
  int cnt = lower_bound(cands + 1, cands + p + 1, b) - cands - 1;
  if (cnt + h >= n) {
    return pf[cnt] + (long long) (n - cnt) * b;
  }
  return pf[n - h] + (long long) h * b;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m >> c;
  for (int i = 1; i <= n; ++i) {
    int x, y; cin >> x >> y;
    pt[i] = {x, y, i};
  }
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j < 4; ++j) {
      cin >> rect[i][j];
    }
  }
  bld();
  for (int i = 1; i <= n; ++i) {
    swap(pt[i][0], pt[i][1]);
  }
  for (int i = 1; i <= m; ++i) {
    swap(rect[i][0], rect[i][1]);
    swap(rect[i][2], rect[i][3]);
  }
  bld();
  fill(lab + 1, lab + n + 1, -1);
  sort(edges.begin(), edges.end());
  for (auto [c, u, v] : edges) {
    if (mrg(u, v)) {
      cands[++p] = c;
      pf[p] = pf[p - 1] + c;
    }
  }
  while (c--) {
    int b, h; cin >> b >> h;
    cout << qry(b, h) << "\n";
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30