oj.uz

Submission #283738

# Submission time Handle Problem Language Result Execution time Memory
283738 2020-08-26T06:33:30 Z kdh9949 도로 건설 사업 (JOI13_construction) C++17
100 / 100
 2237 ms 84964 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20128 KB Output is correct
2 Correct 530 ms 49500 KB Output is correct
3 Correct 470 ms 49756 KB Output is correct
4 Correct 473 ms 76348 KB Output is correct
5 Correct 545 ms 75996 KB Output is correct
6 Correct 466 ms 51164 KB Output is correct
7 Correct 379 ms 77772 KB Output is correct
8 Correct 330 ms 76260 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20128 KB Output is correct
2 Correct 530 ms 49500 KB Output is correct
3 Correct 470 ms 49756 KB Output is correct
4 Correct 473 ms 76348 KB Output is correct
5 Correct 545 ms 75996 KB Output is correct
6 Correct 466 ms 51164 KB Output is correct
7 Correct 379 ms 77772 KB Output is correct
8 Correct 330 ms 76260 KB Output is correct
9 Correct 1174 ms 64116 KB Output is correct
10 Correct 1147 ms 64192 KB Output is correct
11 Correct 1101 ms 64196 KB Output is correct
12 Correct 1107 ms 64376 KB Output is correct
13 Correct 816 ms 59912 KB Output is correct
14 Correct 583 ms 76228 KB Output is correct
15 Correct 1096 ms 63500 KB Output is correct
16 Correct 553 ms 81148 KB Output is correct
17 Correct 531 ms 77924 KB Output is correct
18 Correct 642 ms 68492 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20128 KB Output is correct
2 Correct 530 ms 49500 KB Output is correct
3 Correct 470 ms 49756 KB Output is correct
4 Correct 473 ms 76348 KB Output is correct
5 Correct 545 ms 75996 KB Output is correct
6 Correct 466 ms 51164 KB Output is correct
7 Correct 379 ms 77772 KB Output is correct
8 Correct 330 ms 76260 KB Output is correct
9 Correct 782 ms 57692 KB Output is correct
10 Correct 1436 ms 70364 KB Output is correct
11 Correct 1111 ms 53084 KB Output is correct
12 Correct 1737 ms 83256 KB Output is correct
13 Correct 812 ms 45920 KB Output is correct
14 Correct 1819 ms 73160 KB Output is correct
15 Correct 761 ms 58332 KB Output is correct
16 Correct 733 ms 56316 KB Output is correct
17 Correct 1628 ms 83224 KB Output is correct
18 Correct 1783 ms 80712 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 20128 KB Output is correct
2 Correct 530 ms 49500 KB Output is correct
3 Correct 470 ms 49756 KB Output is correct
4 Correct 473 ms 76348 KB Output is correct
5 Correct 545 ms 75996 KB Output is correct
6 Correct 466 ms 51164 KB Output is correct
7 Correct 379 ms 77772 KB Output is correct
8 Correct 330 ms 76260 KB Output is correct
9 Correct 1174 ms 64116 KB Output is correct
10 Correct 1147 ms 64192 KB Output is correct
11 Correct 1101 ms 64196 KB Output is correct
12 Correct 1107 ms 64376 KB Output is correct
13 Correct 816 ms 59912 KB Output is correct
14 Correct 583 ms 76228 KB Output is correct
15 Correct 1096 ms 63500 KB Output is correct
16 Correct 553 ms 81148 KB Output is correct
17 Correct 531 ms 77924 KB Output is correct
18 Correct 642 ms 68492 KB Output is correct
19 Correct 782 ms 57692 KB Output is correct
20 Correct 1436 ms 70364 KB Output is correct
21 Correct 1111 ms 53084 KB Output is correct
22 Correct 1737 ms 83256 KB Output is correct
23 Correct 812 ms 45920 KB Output is correct
24 Correct 1819 ms 73160 KB Output is correct
25 Correct 761 ms 58332 KB Output is correct
26 Correct 733 ms 56316 KB Output is correct
27 Correct 1628 ms 83224 KB Output is correct
28 Correct 1783 ms 80712 KB Output is correct
29 Correct 1351 ms 69468 KB Output is correct
30 Correct 974 ms 53124 KB Output is correct
31 Correct 1248 ms 61448 KB Output is correct
32 Correct 682 ms 42548 KB Output is correct
33 Correct 1272 ms 63176 KB Output is correct
34 Correct 718 ms 42820 KB Output is correct
35 Correct 1412 ms 63740 KB Output is correct
36 Correct 1375 ms 61612 KB Output is correct
37 Correct 1878 ms 84964 KB Output is correct
38 Correct 1451 ms 70024 KB Output is correct
39 Correct 2237 ms 78180 KB Output is correct