#include <bits/stdc++.h>
#define ff(i,a,b) for(int i=(a), _b=(b); i<=_b; ++i)
#define gg(i,a,b) for(int i=(a), _b=(b); i>=_b; --i)
#define REP(i,b) for(int i=(0), _b=(b); i< _b; ++i)
#define endl '\n'
#define long long long
#define ALL(x) (x).begin(), (x).end()
#define Love(a) {cerr << #a << " = " << a << endl;}
#define _ << "," <<
#define BIT(i, x) (((x)>>(i))&1)
#define X first
#define Y second
#define gc getchar
#define pc putchar
#define NAME "Construction"
using namespace std;
const int N = 2e5 + 8, maxQ = 5e5 + 7;
typedef pair<int, int> ii;
inline void read(int &x){
register int c = gc();
x = 0;
int neg = 0;
for (;((c<48 || c>57) && c != '-') ;c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
inline void writeln(long x){
char buffor[21];
register int i=0;
int neg=0; if (x<0) {neg=1; x= -x;}
do{
buffor[i++]=(x%10)+'0';
x/=10;
} while(x);
i--;
if (neg) pc('-');
while(i>=0) pc(buffor[i--]);
pc('\n');
}
struct HCN {
int x, y, u, v;
HCN () {}
HCN (int x, int y, int u, int v) : x(x), y(y), u(u), v(v) {}
}rect[N];
struct Doan {
int x, l, r;
bool open;
Doan () {}
Doan (int x, int l, int r, bool open) : x(x), l(l), r(r), open(open) {}
bool operator < (const Doan &b) {return x < b.x;}
void print() {
cerr << x << ' ' << l << ' ' << r << ' ' << open << endl;
}
}Line[2*N];
struct edge {
int x, y, w;
edge () {}
edge (int x, int y, int w) : x(x), y(y), w(w) {}
bool operator < (const edge &b) {return w < b.w;};
}e[2*N];
struct Tree {
int lazy[12*N], L[12*N], H[12*N];
long s[12*N];
void Build(int x, int low, int high) {
L[x] = low;
H[x] = high;
s[x] = lazy[x] = 0;
if (low < high) {
int mid = (low + high) / 2;
Build(2*x, low, mid);
Build(2*x+1, mid+1, high);
}
}
void Down(int x) {
int w = lazy[x];
lazy[2*x] += w;
lazy[2*x+1] += w;
s[2*x] += 1ll * w * (H[2*x] - L[2*x] + 1);
s[2*x+1] += 1ll * w * (H[2*x+1] - L[2*x+1] + 1);
lazy[x] = 0;
}
void Update(int x, int i, int j, int w) {
if (L[x] > j || H[x] < i) return;
if (i <= L[x] && H[x] <= j) {
s[x] += 1ll * w * (H[x] - L[x] + 1);
lazy[x] += w;
return;
}
Down(x);
Update(2*x, i, j, w);
Update(2*x+1, i, j, w);
s[x] = s[2*x] + s[2*x+1];
}
long Query(int x, int i, int j) {
if (L[x] > j || H[x] < i) return 0;
if (i <= L[x] && H[x] <= j) return s[x];
Down(x);
return Query(2*x, i, j) + Query(2*x+1, i, j);
}
}it;
struct Quest {
int w, cnt, id;
Quest () {}
bool operator < (const Quest &b) {return w < b.w;}
}q[maxQ];
int n, m, Q, rankX, rankY, E, lab[N], TPLT;
long ans[maxQ], pre[N];
ii a[N], save[N];
map <int, int> mapX, mapY;
map <ii, int> city;
void Enter() {
read(n);
read(m);
read(Q);
ff(i, 1, n) {
read(a[i].X); read(a[i].Y);
save[i] = a[i];
city[a[i]] = i;
}
ff(i, 1, m) {
read(rect[i].x);
read(rect[i].y);
read(rect[i].u);
read(rect[i].v);
}
}
void Ranking() {
mapX.clear();
mapY.clear();
ff(i, 1, n) {
mapX[a[i].X] = 1;
mapY[a[i].Y] = 1;
}
ff(i, 1, m) {
mapX[rect[i].x] = 1;
mapX[rect[i].u] = 1;
mapY[rect[i].y] = 1;
mapY[rect[i].v] = 1;
}
rankX = 0;
for (map<int, int> :: iterator it = mapX.begin(); it != mapX.end(); ++it) mapX[it->X] = ++rankX;
rankY = 0;
for (map<int, int> :: iterator it = mapY.begin(); it != mapY.end(); ++it) mapY[it->X] = ++rankY;
}
void CreateLine() {
ff(i, 1, m) {
Line[i] = Doan(mapX[rect[i].x], mapY[rect[i].y], mapY[rect[i].v], 1);
Line[i+m] = Doan(mapX[rect[i].u], mapY[rect[i].y], mapY[rect[i].v], 0);
}
sort(Line+1, Line+1+2*m);
// ff(i, 1, 2*m) {
// Love(i); Line[i].print();
// }
}
void Duyet(int &k, int stop) {
while (k <= n && mapX[a[k].X] < stop) {
if (k > 1 && a[k].X == a[k-1].X && it.Query(1, mapY[a[k-1].Y], mapY[a[k].Y]) == 0) {
e[++E] = edge(city[a[k]], city[a[k-1]], a[k].Y - a[k-1].Y);
}
++k;
}
}
void BuildEdge() {
Ranking();
CreateLine();
sort(a+1, a+1+n); //sort cac diem theo x tang dan, x = nhau thi y tang dan
//ff(i, 1, n) Love(i _ a[i].X _ a[i].Y)
it.Build(1, 1, rankY);
int k = 1, j = 1;
vector <ii> v;
Duyet(k, Line[1].x);
Line[2*m+1].x = 1e9 + 7;
for (int i = 1; i <= 2*m; i = ++j) {
while (j < 2*m && Line[j+1].x == Line[i].x) ++j;
ff(z, i, j)
if (Line[z].open) it.Update(1, Line[z].l, Line[z].r, 1);
while (k <= n && mapX[a[k].X] == Line[i].x) {
v.push_back(a[k]);
++k;
}
ff(z, 1, v.size()-1) {
if (!it.Query(1, mapY[v[z-1].Y], mapY[v[z].Y])) {
e[++E] = edge(city[v[z]], city[v[z-1]], v[z].Y - v[z-1].Y);
}
}
//Love(v.size())
ff(z, i, j)
if (!Line[z].open) it.Update(1, Line[z].l, Line[z].r, -1);
Duyet(k, Line[j+1].x);
//Love(i _ j _ v.size())
v.clear();
}
}
void Reverse() {
city.clear();
ff(i, 1, n) {
swap(a[i].X , a[i].Y);
swap(save[i].X, save[i].Y);
city[save[i]] = i;
}
ff(i, 1, m) {
swap(rect[i].x, rect[i].y);
swap(rect[i].u, rect[i].v);
}
}
int FindSet(int u) {
return lab[u] < 0 ? u : lab[u] = FindSet(lab[u]);
}
void Union(int r, int s) {
--TPLT;
if (lab[r] < lab[s]) swap(r, s);
if (lab[r] == lab[s]) lab[s]--;
lab[r] = s;
}
void Answer() {
sort(e+1, e+1+E);
// ff(i, 1, Q) {
// cin >> q[i].w >> q[i].cnt;
// q[i].id = i;
// }
//
// sort(q+1, q+1+Q);
fill_n(lab, n+1, -1);
TPLT = n;
vector <int> v;
long res = 0;
ff(i, 1, E) {
int r = FindSet(e[i].x), s = FindSet(e[i].y);
if (r != s) {
Union(r, s);
res += e[i].w;
v.push_back(e[i].w);
}
}
int top = v.size();
REP(i, top) pre[i] = (i == 0 ? v[i] : pre[i-1] + v[i]);
ff(i, 1, Q) {
int w, cnt;
read(w); read(cnt);
if (cnt < TPLT) writeln(-1);
else {
//if (v.back() <= w) cout << pre[top-1] + 1ll * w * TPLT << endl;
int x = v.end() - upper_bound(ALL(v), w);
int can = min(cnt - TPLT, x);
long ans = (can == top ? 0 : pre[top-can-1]) + 1ll * (can + TPLT) * w;
writeln(ans);
}
}
}
void Process() {
BuildEdge();
Reverse();
BuildEdge();
// ff(i, 1, E) Love(e[i].x _ e[i].y _ e[i].w)
Answer();
}
int main() {
//ios_base::sync_with_stdio(0); cin.tie(0);
//freopen(NAME".inp", "r", stdin);
// freopen(NAME".out", "w", stdout);
Enter();
Process();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
79688 KB |
Output is correct |
| 2 |
Correct |
2009 ms |
101452 KB |
Output is correct |
| 3 |
Correct |
1839 ms |
101028 KB |
Output is correct |
| 4 |
Correct |
1089 ms |
92732 KB |
Output is correct |
| 5 |
Correct |
1849 ms |
101732 KB |
Output is correct |
| 6 |
Correct |
1879 ms |
100980 KB |
Output is correct |
| 7 |
Correct |
503 ms |
92400 KB |
Output is correct |
| 8 |
Correct |
1169 ms |
101740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5000 ms |
137636 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2106 ms |
100980 KB |
Output is correct |
| 2 |
Correct |
2025 ms |
101748 KB |
Output is correct |
| 3 |
Correct |
1999 ms |
101452 KB |
Output is correct |
| 4 |
Correct |
1233 ms |
92780 KB |
Output is correct |
| 5 |
Correct |
2043 ms |
105284 KB |
Output is correct |
| 6 |
Correct |
2499 ms |
104076 KB |
Output is correct |
| 7 |
Correct |
2109 ms |
100980 KB |
Output is correct |
| 8 |
Correct |
2099 ms |
100980 KB |
Output is correct |
| 9 |
Correct |
679 ms |
92400 KB |
Output is correct |
| 10 |
Correct |
1383 ms |
101740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5000 ms |
137636 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
