#include <bits/stdc++.h>
using namespace std;
using pii = pair<long long, long long>;
#define ff first
#define ss second
#define eack emplace_back
#define pack push_back
vector<long long> xx, yy;
vector<pii> in, xnode[600005], ynode[600005];
vector<pair<pii, pii> > in2, xsp, ysp;
long long W[200005];
long long upa[200005];
long long fnd(long long x) {return upa[x] == x ? x : upa[x] = fnd(upa[x]);}
bool uni(long long x, long long y) {
x = fnd(x), y = fnd(y);
if (x == y) return 0;
upa[y] = x;
return 1;
}
const long long SIZE = 1 << 20;
struct ST {
long long V[2 * SIZE], L[2 * SIZE];
long long sz;
void init() {
memset(V, 0, sizeof(V));
memset(L, 0, sizeof(L));
}
void Ldown(long long nn, long long s, long long m, long long e) {
L[nn << 1] += L[nn];
L[nn << 1 | 1] += L[nn];
V[nn << 1] += L[nn] * (m - s + 1);
V[nn << 1 | 1] += L[nn] * (e - m);
L[nn] = 0;
}
void update(long long s, long long e, long long v, long long nn, long long ns, long long ne) {
if (ns > e || ne < s) return;
if (s <= ns && ne <= e) {
V[nn] += (e - s + 1) * v;
L[nn] += v;
return;
}
long long m = ns + ne >> 1;
Ldown(nn, ns, m, ne);
update(s, e, v, nn << 1, ns, m);
update(s, e, v, nn << 1 | 1, m + 1, ne);
V[nn] = V[nn << 1] + V[nn << 1 | 1];
}
long long query(long long s, long long e, long long nn, long long ns, long long ne) {
if (ns > e || ne < s) return 0;
if (s <= ns && ne <= e) return V[nn];
long long m = ns + ne >> 1;
Ldown(nn, ns, m, ne);
return query(s, e, nn << 1, ns, m) + query(s, e, nn << 1 | 1, m + 1, ne);
}
void update(long long s, long long e, long long v) {
update(s, e, v, 1, 0, sz);
}
long long query(long long s, long long e) {
return query(s, e, 1, 0, sz);
}
} seg;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
long long N, M, C; cin >> N >> M >> C;
for (long long i = 0; i < N; ++i) {
long long x, y; cin >> x >> y;
xx.eack(x);
yy.eack(y);
in.eack(x, y);
}
for (long long i = 0; i < M; ++i) {
long long p, q, r, s; cin >> p >> q >> r >> s;
xx.eack(p); xx.eack(r);
yy.eack(q); yy.eack(s);
in2.eack(pii(p, q), pii(r, s));
}
sort(xx.begin(), xx.end());
sort(yy.begin(), yy.end());
xx.erase(unique(xx.begin(), xx.end()), xx.end());
yy.erase(unique(yy.begin(), yy.end()), yy.end());
iota(upa, upa + N, 0);
for (long long ii = 0; ii < in.size(); ++ii) {
auto i = in[ii];
i.ff = lower_bound(xx.begin(), xx.end(), i.ff) - xx.begin();
i.ss = lower_bound(yy.begin(), yy.end(), i.ss) - yy.begin();
xnode[i.ff].eack(i.ss, ii);
ynode[i.ss].eack(i.ff, ii);
}
for (long long i = 0; i < xx.size(); ++i) sort(xnode[i].begin(), xnode[i].end());
for (long long i = 0; i < yy.size(); ++i) sort(ynode[i].begin(), ynode[i].end());
for (auto i : in2) {
long long p, q, r, s;
tie(p, q) = i.ff;
tie(r, s) = i.ss;
p = lower_bound(xx.begin(), xx.end(), p) - xx.begin();
r = lower_bound(xx.begin(), xx.end(), r) - xx.begin();
q = lower_bound(yy.begin(), yy.end(), q) - yy.begin();
s = lower_bound(yy.begin(), yy.end(), s) - yy.begin();
xsp.eack(pii(p, 1), pii(q, s - 1));
xsp.eack(pii(r + 1, -1), pii(q, s - 1));
ysp.eack(pii(q, 1), pii(p, r - 1));
ysp.eack(pii(s + 1, -1), pii(p, r - 1));
}
sort(xsp.begin(), xsp.end());
sort(ysp.begin(), ysp.end());
vector<pair<long long, pii> > E;
seg.sz = (long long)yy.size() - 2;
for (long long i = 0, si = 0; i < xx.size(); ++i) {
for (; si < xsp.size() && xsp[si].ff.ff <= i; ++si) {
seg.update(xsp[si].ss.ff, xsp[si].ss.ss, xsp[si].ff.ss);
}
auto &vec = xnode[i];
for (long long j = 0; j + 1 < vec.size(); ++j) {
if (seg.query(vec[j].ff, vec[j + 1].ff - 1) == 0) {
E.eack(yy[vec[j + 1].ff] - yy[vec[j].ff], pii(vec[j].ss, vec[j + 1].ss));
}
}
}
seg.init();
seg.sz = (long long)xx.size() - 2;
for (long long i = 0, si = 0; i < yy.size(); ++i) {
for (; si < ysp.size() && ysp[si].ff.ff <= i; ++si) {
seg.update(ysp[si].ss.ff, ysp[si].ss.ss, ysp[si].ff.ss);
}
auto &vec = ynode[i];
for (long long j = 0; j + 1 < vec.size(); ++j) {
if (seg.query(vec[j].ff, vec[j + 1].ff - 1) == 0) {
E.eack(xx[vec[j + 1].ff] - xx[vec[j].ff], pii(vec[j].ss, vec[j + 1].ss));
}
}
}
sort(E.begin(), E.end());
long long K = N;
for (auto i : E) {
if (uni(i.ss.ff, i.ss.ss)) {
--K;
W[K] = W[K + 1] + i.ff;
}
}
vector<pair<pii, long long> > qry(C);
vector<long long> ans(C);
for (long long i = 0; i < C; ++i) {
long long a, b; cin >> a >> b;
qry[i] = {pii(a, b), i};
}
sort(qry.begin(), qry.end());
for (long long i = 0, k = N; i < C; ++i) {
if (qry[i].ff.ss < K) {
ans[qry[i].ss] = -1;
continue;
}
long long a, b; tie(a, b) = qry[i].ff;
while (k > K && W[k] + 1ll * k * a > W[k - 1] + 1ll * (k - 1) * a) --k;
ans[qry[i].ss] = W[min(b, k)] + 1ll * min(b, k) * a;
}
for (auto i : ans) cout << i << '\n';
return 0;
}
Compilation message
construction.cpp: In member function 'void ST::update(long long int, long long int, long long int, long long int, long long int, long long int)':
construction.cpp:45:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
long long m = ns + ne >> 1;
~~~^~~~
construction.cpp: In member function 'long long int ST::query(long long int, long long int, long long int, long long int, long long int)':
construction.cpp:54:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
long long m = ns + ne >> 1;
~~~^~~~
construction.cpp: In function 'int main()':
construction.cpp:89:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (long long ii = 0; ii < in.size(); ++ii) {
~~~^~~~~~~~~~~
construction.cpp:97:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (long long i = 0; i < xx.size(); ++i) sort(xnode[i].begin(), xnode[i].end());
~~^~~~~~~~~~~
construction.cpp:98:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (long long i = 0; i < yy.size(); ++i) sort(ynode[i].begin(), ynode[i].end());
~~^~~~~~~~~~~
construction.cpp:120:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (long long i = 0, si = 0; i < xx.size(); ++i) {
~~^~~~~~~~~~~
construction.cpp:121:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (; si < xsp.size() && xsp[si].ff.ff <= i; ++si) {
~~~^~~~~~~~~~~~
construction.cpp:126:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (long long j = 0; j + 1 < vec.size(); ++j) {
~~~~~~^~~~~~~~~~~~
construction.cpp:136:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (long long i = 0, si = 0; i < yy.size(); ++i) {
~~^~~~~~~~~~~
construction.cpp:137:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (; si < ysp.size() && ysp[si].ff.ff <= i; ++si) {
~~~^~~~~~~~~~~~
construction.cpp:142:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (long long j = 0; j + 1 < vec.size(); ++j) {
~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
63264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1762 ms |
131100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
741 ms |
109388 KB |
Output is correct |
| 2 |
Correct |
741 ms |
108220 KB |
Output is correct |
| 3 |
Correct |
755 ms |
106052 KB |
Output is correct |
| 4 |
Incorrect |
695 ms |
109452 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2028 ms |
140912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
