#include<stdio.h>
#include<algorithm>
#define SZ 1048576
using namespace std;
int n, m, Q, D[201000], par[201000];
long long SS[201000];
struct Rectangle{
int x1, x2, y1, y2;
}Rect[201000];
struct Seg{
int x, y1, y2, ck;
bool operator<(const Seg &p)const{
return x < p.x;
}
}S[401000];
struct point{
int x, y, num;
bool operator<(const point &p)const{
return x != p.x ? x < p.x : y < p.y;
}
}w[201000], Tw[201000];
struct order{
int y, num;
bool operator<(const order &p)const{
return y < p.y;
}
}Y[601000];
struct Edge{
int a, b, d;
bool operator<(const Edge &p)const{
return d < p.d;
}
}E[401000];
int cnt;
struct SegTree{
long long S;
int K;
}IT[SZ+SZ+2];
void Add2(int nd, int b, int e, int x){
IT[nd].K += x;
IT[nd].S += (long long)(e - b + 1)*x;
return;
}
void spread(int nd, int b, int e){
if (!IT[nd].K)return;
Add2(nd * 2, b, m, IT[nd].K);
Add2(nd * 2 + 1, m + 1, e, IT[nd].K);
IT[nd].K = 0;
}
void Add(int nd, int b, int e, int s, int l, int x){
if (b == s && e == l){
Add2(nd, b, e, x);
return;
}
int m = (b + e) >> 1;
spread(nd, b, e);
if (s <= m)Add(nd * 2, b, m, s, min(m, l), x);
if (l > m)Add(nd * 2 + 1, m + 1, e, max(m + 1, s), l, x);
IT[nd].S = IT[nd * 2].S + IT[nd * 2 + 1].S;
}
long long Sum(int nd, int b, int e, int s, int l){
long long r = 0;
if (b == s && e == l)return IT[nd].S;
int m = (b + e) >> 1;
spread(nd, b, e);
if (s <= m)r += Sum(nd * 2, b, m, s, min(m, l));
if (l > m)r += Sum(nd * 2 + 1, m + 1, e, max(m + 1, s), l);
return r;
}
void Do(){
int i, t = 0, pv;
for (i = 1; i <= n; i++){
Y[i].y = w[i].y, Y[i].num = i;
Tw[i].x = w[i].x, Tw[i].num = i;
}
for (i = 1; i <= m; i++){
Y[i + n].y = Rect[i].y1, Y[i + n].num = i + n;
Y[i + n + m].y = Rect[i].y2, Y[i + n + m].num = i + n + m;
}
sort(Y + 1, Y + n + m + m + 1);
for (i = 1; i <= n + m + m; i++){
if (i == 1 || Y[i].y != Y[t].y)t = i;
if (Y[i].num <= n)Tw[Y[i].num].y = t;
else if (Y[i].num <= n + m)Rect[Y[i].num - n].y1 = t;
else Rect[Y[i].num - n - m].y2 = t;
}
for (i = 1; i <= m; i++){
S[i].y1 = S[i + m].y1 = Rect[i].y1, S[i].y2 = S[i + m].y2 = Rect[i].y2;
S[i].x = Rect[i].x1, S[i + m].x = Rect[i].x2 + 1;
S[i].ck = 1, S[i + m].ck = -1;
}
sort(Tw, Tw + n + 1);
sort(S + 1, S + m + m + 1);
pv = 1;
for (i = 1; i <= m + m + 1; i++){
while (pv + 1 <= n && (i == m + m + 1 || Tw[pv + 1].x < S[i].x)){
if (Tw[pv].x == Tw[pv + 1].x){
if (!Sum(1, 1, SZ, Tw[pv].y, Tw[pv + 1].y)){
E[cnt].a = Tw[pv].num, E[cnt].b = Tw[pv + 1].num, E[cnt].d = Y[Tw[pv + 1].y].y - Y[Tw[pv].y].y;
cnt++;
}
}
pv++;
}
if (i == m + m + 1)break;
Add(1, 1, SZ, S[i].y1, S[i].y2, S[i].ck);
}
for (i = 1; i <= m; i++){
Rect[i].y1 = Y[Rect[i].y1].y;
Rect[i].y2 = Y[Rect[i].y2].y;
}
}
int find(int a){
return a == par[a] ? a : par[a] = find(par[a]);
}
int main(){
int i, c = 0, a, b, be, ed, mid, r;
scanf("%d%d%d", &n, &m, &Q);
for (i = 1; i <= n; i++){
scanf("%d%d", &w[i].x, &w[i].y);
}
for (i = 1; i <= m; i++){
scanf("%d%d%d%d", &Rect[i].x1, &Rect[i].y1, &Rect[i].x2, &Rect[i].y2);
}
Do();
for (i = 1; i <= n; i++){
swap(w[i].x, w[i].y);
}
for (i = 1; i <= m; i++){
swap(Rect[i].x1, Rect[i].y1);
swap(Rect[i].x2, Rect[i].y2);
}
Do();
sort(E, E + cnt);
for (i = 1; i <= n; i++)par[i] = i;
for (i = 0; i < cnt; i++){
a = find(E[i].a), b = find(E[i].b);
if (a != b){
par[a] = b;
D[++c] = E[i].d;
SS[c] = SS[c - 1] + D[c];
}
}
long long Res;
while (Q--){
scanf("%d%d", &a, &b);
if (b + c < n){
printf("-1\n");
continue;
}
be = 1, ed = c, r = 0;
while (be <= ed){
mid = (be + ed) >> 1;
if (D[mid] <= a){
r = mid; be = mid + 1;
}
else ed = mid - 1;
}
if (b < n - r)Res = (long long)b*a + SS[n - b];
else Res = (long long)(n - r)*a + SS[r];
printf("%lld\n", Res);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
60516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1408 ms |
60516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
576 ms |
60516 KB |
Output is correct |
| 2 |
Correct |
540 ms |
60516 KB |
Output is correct |
| 3 |
Correct |
512 ms |
60516 KB |
Output is correct |
| 4 |
Incorrect |
588 ms |
60516 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1612 ms |
60516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
