제출 #283738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
283738		kdh9949	도로 건설 사업 (JOI13_construction)	C++17	100 / 100	2237 ms	84964 KiB

construction

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

using po = pair<pii, int>;
const ll INF = ll(1e18);

namespace Fen {
  const static int N = 600005;
  int d[N];

  void i(){ memset(d, 0, sizeof(d)); }
  void u(int x, int v){ for(; x < N; x += x & -x) d[x] += v; }
  void u(int s, int e, int v){ u(s, v); u(e + 1, -v); }
  int g(int x){ int r = 0; for(; x; x &= x - 1) r += d[x]; return r; }
}

namespace Seg {
  const static int sz = 262144;
  struct Cht {
    struct Lin {
      ll a, b;
      ll f(ll x){ return a * x + b; }
    };
    
    vector<Lin> v;
    int sz;

    int pop(Lin p, Lin q, Lin r) {
      return (q.b - p.b) * (p.a - r.a) > (r.b - p.b) * (p.a - q.a);
    }

    void u(ll a, ll b) {
      Lin cur = {a, b};
      while(sz >= 2 && pop(v[sz - 2], v[sz - 1], cur)) { v.pop_back(); sz--; }
      v.push_back(cur); sz++;
    }

    ll g(ll x) {
      if(!sz) return INF;
      int s = 0, e = sz - 1;
      while(s < e) {
        int m = (s + e) / 2;
        if(v[m].f(x) < v[m + 1].f(x)) e = m;
        else s = m + 1;
      }
      return v[s].f(x);
    }
  } d[2 * sz];

  void u(int s, int e, ll a, ll b) {
    for(s += sz, e += sz; s <= e; s /= 2, e /= 2) {
      if(s & 1) d[s++].u(a, b);
      if(~e & 1) d[e--].u(a, b);
    }
  }

  ll g(int k, ll x) {
    ll r = INF;
    for(k += sz; k; k /= 2) r = min(r, d[k].g(x));
    return (r == INF ? -1 : r);
  }
}

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

  int n, m, q;
  cin >> n >> m >> q;

  vector<po> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i].x.x >> a[i].x.y;
    a[i].y = i + 1;
  }

  vector<pair<pii, pii>> b(m);
  for(int i = 0; i < m; i++) {
    cin >> b[i].x.x >> b[i].x.y >> b[i].y.x >> b[i].y.y;
  }

  vector<po> edges;
  auto add_edges = [&]() {
    sort(all(a));
    vint tx, ty, prv(n);
    for(int i = 0; i < n; i++) {
      tx.push_back(a[i].x.x);
      ty.push_back(a[i].x.y);
      if(i && a[i].x.x == a[i - 1].x.x) prv[i] = 1;
    }
    for(int i = 0; i < m; i++) {
      tx.push_back(b[i].x.x);
      tx.push_back(b[i].y.x);
      ty.push_back(b[i].x.y);
    }
    sort(all(tx));
    sort(all(ty));
    
    int Y = ty.size();
    vector<vpii> pv(Y + 1), sv(Y + 1);
    auto cpr = [&](const vint &v, int x) {
      return int(lower_bound(all(v), x) - v.begin()) + 1;
    };
    for(int i = 0; i < n; i++) {
      pv[cpr(ty, a[i].x.y)].emplace_back(cpr(tx, a[i].x.x), i);
    }
    for(int i = 0; i < m; i++) {
      sv[cpr(ty, b[i].x.y)].emplace_back(cpr(tx, b[i].x.x), cpr(tx, b[i].y.x));
    }

    Fen::i();
    vint val(n);
    for(int i = 1; i <= Y; i++) {
      for(pii &p : pv[i]) {
        val[p.y] = Fen::g(p.x);
        if(prv[p.y] && val[p.y - 1] == val[p.y]) {
          edges.emplace_back(pii(a[p.y].y, a[p.y - 1].y), a[p.y].x.y - a[p.y - 1].x.y);
        }
      }
      for(pii &p : sv[i]) Fen::u(p.x, p.y, 1);
    }
  };
  
  add_edges();
  for(int i = 0; i < n; i++) swap(a[i].x.x, a[i].x.y);
  for(int i = 0; i < m; i++) { swap(b[i].x.x, b[i].x.y); swap(b[i].y.x, b[i].y.y); }
  add_edges();

  sort(all(edges), [](po &p, po &q){ return p.y < q.y; });
  vint par(n + 1);
  iota(all(par), 0);
  function<int(int)> f = [&](int x){ return par[x] = (x == par[x] ? x : f(par[x])); };
  int cnt = n;
  ll sum = 0;
  Seg::u(n, n, n, 0);
  for(po &p : edges) {
    if(f(p.x.x) == f(p.x.y)) continue;
    par[f(p.x.y)] = f(p.x.x);
    sum += p.y;
    cnt--;
    Seg::u(cnt, n, cnt, sum);
  }

  while(q--) {
    ll x;
    int h;
    cin >> x >> h;
    cout << Seg::g(h, x) << '\n';
  }

  return 0;
}

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