제출 #283738

#제출 시각아이디문제언어결과실행 시간메모리
283738kdh9949도로 건설 사업 (JOI13_construction)C++17
100 / 100
2237 ms84964 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...