이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |