#include <bits/stdc++.h>
using namespace std;
class segtree {
public:
struct node {
// don't forget to set default value (used for leaves)
// not necessarily neutral element!
int val = 0;
int put = 0;
void apply(int l, int r, int v) {
val += v;
}
};
node unite(const node &a, const node &b) const {
node res;
res.val = max(a.val, b.val);
return res;
}
inline void push(int x, int l, int r) {
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
if (tree[x].put != 0) {
tree[x + 1].apply(l, y, tree[x].put);
tree[z].apply(y + 1, r, tree[x].put);
tree[x].put = 0;
}
}
inline void pull(int x, int z) {
tree[x] = unite(tree[x + 1], tree[z]);
}
int n;
vector<node> tree;
void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y);
build(z, y + 1, r);
pull(x, z);
}
template <typename M>
void build(int x, int l, int r, const vector<M> &v) {
if (l == r) {
tree[x].apply(l, r, v[l]);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y, v);
build(z, y + 1, r, v);
pull(x, z);
}
node get(int x, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return tree[x];
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
node res{};
if (rr <= y) {
res = get(x + 1, l, y, ll, rr);
} else {
if (ll > y) {
res = get(z, y + 1, r, ll, rr);
} else {
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
}
pull(x, z);
return res;
}
template <typename... M>
void modify(int x, int l, int r, int ll, int rr, const M&... v) {
if (ll <= l && r <= rr) {
tree[x].apply(l, r, v...);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
if (ll <= y) {
modify(x + 1, l, y, ll, rr, v...);
}
if (rr > y) {
modify(z, y + 1, r, ll, rr, v...);
}
pull(x, z);
}
int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res;
if (f(tree[x + 1])) {
res = find_first_knowingly(x + 1, l, y, f);
} else {
res = find_first_knowingly(z, y + 1, r, f);
}
pull(x, z);
return res;
}
int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
if (!f(tree[x])) {
return -1;
}
return find_first_knowingly(x, l, r, f);
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res = -1;
if (ll <= y) {
res = find_first(x + 1, l, y, ll, rr, f);
}
if (rr > y && res == -1) {
res = find_first(z, y + 1, r, ll, rr, f);
}
pull(x, z);
return res;
}
int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res;
if (f(tree[z])) {
res = find_last_knowingly(z, y + 1, r, f);
} else {
res = find_last_knowingly(x + 1, l, y, f);
}
pull(x, z);
return res;
}
int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
if (!f(tree[x])) {
return -1;
}
return find_last_knowingly(x, l, r, f);
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res = -1;
if (rr > y) {
res = find_last(z, y + 1, r, ll, rr, f);
}
if (ll <= y && res == -1) {
res = find_last(x + 1, l, y, ll, rr, f);
}
pull(x, z);
return res;
}
segtree(int _n) : n(_n) {
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}
template <typename M>
segtree(const vector<M> &v) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v);
}
node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return get(0, 0, n - 1, ll, rr);
}
node get(int p) {
assert(0 <= p && p <= n - 1);
return get(0, 0, n - 1, p, p);
}
template <typename... M>
void modify(int ll, int rr, const M&... v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
modify(0, 0, n - 1, ll, rr, v...);
}
// find_first and find_last call all FALSE elements
// to the left (right) of the sought position exactly once
int find_first(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return find_first(0, 0, n - 1, ll, rr, f);
}
int find_last(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return find_last(0, 0, n - 1, ll, rr, f);
}
};
struct dsu {
vector<int> p;
dsu(int n) {
p.resize(n, -1);
}
int get(int x) {
return p[x] < 0 ? x : p[x] = get(p[x]);
}
int unite(int x, int y) {
x = get(x); y = get(y);
if (x != y) {
if (p[x] < p[y]) swap(x, y);
p[y] += p[x];
p[x] = y;
return 1;
}
return 0;
}
};
struct node {
long long a, b;
node(long long a = 0, long long b = 1e18) : a(a), b(b) {
}
long long get(int x) {
return a * x + b;
}
};
struct Eins {
vector<node> st;
vector<int> b;
int n;
Eins(vector<int> &b) : b(b) {
n = (int) b.size();
st.resize(n << 2 | 1);
}
void modify(int id, int l, int r, node val) {
int mid = l + r >> 1;
if (st[id].get(b[mid]) > val.get(b[mid])) swap(val, st[id]);
if (l == r) return ;
if (st[id].get(b[l]) > val.get(b[l])) modify(id << 1, l, mid, val);
if (st[id].get(b[r]) > val.get(b[r])) modify(id << 1|1, mid + 1, r, val);
}
long long get(int id, int l, int r, int x) {
long long ans = st[id].get(x);
if (l == r) return ans;
int mid = l + r >> 1;
if (x <= b[mid]) return min(ans, get(id << 1, l, mid, x));
return min(ans, get(id << 1|1, mid + 1, r, x));
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
#define getp(a, x) get<x>(a)
int n, m, q;
cin >> n >> m >> q;
vector<pair<int,int>> a(n);
vector<int> b;
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
b.push_back(a[i].first);
b.push_back(a[i].second);
}
vector<tuple<int, int, int, int>> ban;
for (int i = 0; i < m; i++) {
int u, v, x, y;
cin >> u >> v >> x >> y;
ban.emplace_back(u, v, x, y);
b.push_back(u);
b.push_back(v);
b.push_back(x);
b.push_back(y);
}
sort(b.begin(), b.end());
b.resize(unique(b.begin(), b.end()) - b.begin());
auto find = [&](int x) {return lower_bound(b.begin(), b.end(), x) - b.begin();};
for (int i = 0; i < n; i++) {
a[i].first = find(a[i].first);
a[i].second = find(a[i].second);
}
for (int i = 0; i < m; i++) {
getp(ban[i], 0) = find(getp(ban[i], 0));
getp(ban[i], 1) = find(getp(ban[i], 1));
getp(ban[i], 2) = find(getp(ban[i], 2));
getp(ban[i], 3) = find(getp(ban[i], 3));
}
vector<tuple<int,int,int>> edges;
auto solve = [&]() {
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int x, int y) {
return a[x] < a[y];
});
vector<vector<tuple<int,int,int>>> inner((int) b.size());
for (auto& x : ban) {
inner[getp(x, 0)].emplace_back(getp(x, 1), getp(x, 3), 1);
if (getp(x, 2) + 1 < (int) b.size()) inner[getp(x, 2) + 1].emplace_back(getp(x, 1), getp(x, 3), -1);
}
int pos = 0;
segtree Tree((int) b.size());
for (int i = 0, j; i < n; i = j) {
j = i;
while (j < n && a[id[i]].first == a[id[j]].first) j++;
while (pos <= a[id[i]].first) {
for (auto&x : inner[pos]) {
Tree.modify(getp(x, 0), getp(x, 1), getp(x, 2));
}
pos++;
}
for (int k = j - 1; k > i; k--) {
if (Tree.get(a[id[k - 1]].second, a[id[k]].second).val == 0) edges.emplace_back(b[a[id[k]].second] - b[a[id[k-1]].second], id[k-1], id[k]);
}
}
};
solve();
for (int i = 0; i < n; i++) swap(a[i].first, a[i].second);
for (int i = 0; i < m; i++) {
auto &x = ban[i];
swap(getp(x, 0), getp(x, 1));
swap(getp(x, 2), getp(x, 3));
}
solve();
sort(edges.begin(), edges.end());
int last = n;
vector<long long> ab(n + 1);
dsu d(n);
for (auto& x : edges) {
if (d.unite(getp(x, 1), getp(x, 2))) {
--last;
ab[last] = ab[last + 1] + getp(x, 0);
}
}
vector<vector<pair<int,int>>> Query(n + 1);
b.clear();
for (int i = 0; i < q; i++) {
int c, h;
cin >> c >> h;
Query[h].emplace_back(c, i);
b.push_back(c);
}
sort(b.begin(), b.end());
b.resize(unique(b.begin(), b.end()) - b.begin());
vector<long long> ans(q);
Eins Tree(b);
for (int i = 0; i <= n; i++) {
if (i >= last) {
Tree.modify(1, 0, Tree.n - 1, node(i, ab[i]));
}
for (auto&x : Query[i]) {
if (i < last) ans[x.second] = -1;
else {
ans[x.second] = Tree.get(1, 0, Tree.n - 1, x.first);
}
}
}
for (int i = 0; i < q; i++) cout << ans[i] <<"\n";
}
Compilation message
construction.cpp: In member function 'void Eins::modify(int, int, int, node)':
construction.cpp:262:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
262 | int mid = l + r >> 1;
| ~~^~~
construction.cpp: In member function 'long long int Eins::get(int, int, int, int)':
construction.cpp:271:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
271 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
2328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
2328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
2328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
2328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
