#include <bits/stdc++.h>
#define mp make_pair
#define X first
#define Y second
using namespace std;
template<typename T> inline void read(T &x){
x = 0; char ch;
while(!isdigit(ch=getchar()));
do{x=10*x+ch-'0';}while(isdigit(ch=getchar()));
}
template<typename T> inline void write(T x) {
if (x < 0) {
putchar('-');
write(-x);return;
}
if (x < 10) {
putchar(char(x + 48));
}
else {
write(x/10);
putchar(char(48 + x%10));
}
}
template<typename T> inline void writeln(T x) {
write(x); putchar('\n');
}
typedef long long ll;
const int N = 2e5+111;
int n, m, k, pos[3*N], num, cnt, ID[3*N], Fa[N], eNum;
ll D[3*N], F[N];
struct pt{
int x, y;
ll rx, ry;
pt(){}
pt(int a, int b){
x = a; y = b;
rx = (ll)x; ry = (ll)y;
}
} P[3*N];
struct data{
int x;
int y, l, r;
int type, id;
ll rx;
data(){}
data(int a, int b, int c, int d, int e, int f){
x = a; y = b; l = c; r = d; type = e; id = f;
}
};
vector<data> T;
struct Edge{
int u, v;
ll w;
Edge(){}
Edge(int a, int b, ll c){
u = a; v = b; w = c;
}
} E[4*N];
bool cmp_x(int a, int b){
return P[a].x < P[b].x;
}
bool cmp_y(int a, int b){
return P[a].y < P[b].y;
}
bool operator < (const data &a, const data &b){
return a.x < b.x || (a.x==b.x&&a.type<b.type);
}
bool operator < (const Edge &a, const Edge &b){
return a.w < b.w;
}
void compress(){
num = n+2*m;
for(int i = 1; i <= num; i++){
pos[i] = i;
}
sort(pos+1,pos+num+1,cmp_x);
cnt = 1;
int cur = P[pos[1]].x;
P[pos[1]].x = 1;
for(int i = 2; i <= num; i++){
if(P[pos[i]].x!=cur){
cnt++;
cur = P[pos[i]].x;
}
P[pos[i]].x = cnt;
}
sort(pos+1,pos+num+1,cmp_y);
cnt = 1;
cur = P[pos[1]].y;
P[pos[1]].y = 1;
for(int i = 2; i <= num; i++){
if(P[pos[i]].y!=cur){
cnt++;
cur = P[pos[i]].y;
}
P[pos[i]].y = cnt;
}
}
struct SegTree{
int ST[12*N], Lazy[12*N];
void reset(){
memset(ST,255,sizeof(ST));
memset(Lazy,255,sizeof(Lazy));
}
void down(int id, int l, int r){
if(Lazy[id]==-1) return;
ST[id] = max(ST[id],Lazy[id]);
if(l!=r){
Lazy[2*id] = max(Lazy[2*id],Lazy[id]);
Lazy[2*id+1] = max(Lazy[2*id+1],Lazy[id]);
}
Lazy[id] = -1;
}
void upgrade(int id, int l, int r, int u, int v, int val){
down(id,l,r);
if(r<u||v<l) return;
if(u<=l&&r<=v){
Lazy[id] = max(Lazy[id],val);
down(id,l,r);
return;
}
int mid = (l+r)>>1;
upgrade(2*id,l,mid,u,v,val);
upgrade(2*id+1,mid+1,r,u,v,val);
ST[id] = ST[2*id]+ST[2*id+1];
}
int get(int id, int l, int r, int x){
down(id,l,r);
if(x<l||r<x) return -1;
if(l==r) return ST[id];
int mid = (l+r)>>1;
return max(get(2*id,l,mid,x),get(2*id+1,mid+1,r,x));
}
} Tree;
void makeGraph(){
sort(T.begin(),T.end());
memset(D,255,sizeof(D));
Tree.reset();
for(int i = 0; i < (int)T.size(); i++){
data dt = T[i];
if(dt.type==0) Tree.upgrade(1,1,num,dt.l,dt.r,dt.x);
else{
if(D[dt.y]==-1){
D[dt.y] = dt.x;
ID[dt.y] = dt.id;
}
else{
ll x = (ll)Tree.get(1,1,num,dt.y);
int id = ID[dt.y];
ll xx = D[dt.y];
if(xx>x){
E[++eNum] = Edge(dt.id,id,abs(xx-dt.x));
}
D[dt.y] = dt.x;
ID[dt.y] = dt.id;
}
}
}
}
int root(int x){
if(Fa[x]<0) return x;
int t = root(Fa[x]);
return Fa[x] = t;
}
void unite(int x, int y){
if(Fa[x]<Fa[y]){
Fa[x] += Fa[y];
Fa[y] = x;
}
else{
Fa[y] += Fa[x];
Fa[x] = y;
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
read(n); read(m); read(k);
for(int i = 1; i <= n; i++){
int x, y;
read(x); read(y);
P[i] = pt(x,y);
}
for(int i = 1; i < 2*m; i+=2){
int a, b, c, d;
read(a); read(b); read(c); read(d);
P[n+i] = pt(a,b);
P[n+i+1] = pt(c,d);
}
compress();
for(int i = 1; i <= n; i++){
T.push_back(data(P[i].rx,P[i].y,0,0,1,i));
}
for(int i = 1; i < 2*m; i+=2){
//T.push_back(data(B[i].up.x,0,B[i].up.y,B[i].down.y,0,0,0));
T.push_back(data(P[i+n+1].rx,0,P[i+n].y,P[i+n+1].y,0,0));
}
makeGraph();
T.clear();
for(int i = 1; i <= n; i++){
T.push_back(data(P[i].ry,P[i].x,0,0,1,i));
}
for(int i = 1; i < 2*m; i+=2){
//T.push_back(data(B[i].up.y,0,B[i].up.x,B[i].down.x,0,0,0));
T.push_back(data(P[i+n+1].ry,0,P[i+n].x,P[i+n+1].x,0,0));
}
makeGraph();
sort(E+1,E+eNum+1);
memset(Fa,255,sizeof(Fa));
int com = n;
ll sum = 0;
for(int i = 1; i <= eNum; i++){
int u = E[i].u;
int v = E[i].v;
ll w = E[i].w;
int ru = root(u);
int rv = root(v);
if(ru==rv) continue;
unite(ru,rv);
com--;
sum += w;
F[com] = sum;
}
while(k--){
ll c;
int h;
read(c); read(h);
if(h<com) writeln(-1);
else{
int l = com, r = h;
int ml = floor((double)(l+l+r)/3);
int mr = ceil((double)(l+r+r)/3);
while(ml<mr){
if(F[ml]+c*(ll)ml<F[mr]+c*(ll)mr) r = mr-1;
else l = ml+1;
ml = floor((double)(l+l+r)/3);
mr = ceil((double)(l+r+r)/3);
}
ll res = F[ml]+c*(ll)ml;
writeln(res);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
60072 KB |
Output is correct |
| 2 |
Correct |
279 ms |
71592 KB |
Output is correct |
| 3 |
Correct |
259 ms |
71592 KB |
Output is correct |
| 4 |
Correct |
246 ms |
71592 KB |
Output is correct |
| 5 |
Correct |
266 ms |
71592 KB |
Output is correct |
| 6 |
Correct |
263 ms |
71592 KB |
Output is correct |
| 7 |
Correct |
216 ms |
71592 KB |
Output is correct |
| 8 |
Correct |
173 ms |
71592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1323 ms |
83880 KB |
Output is correct |
| 2 |
Correct |
1263 ms |
83880 KB |
Output is correct |
| 3 |
Correct |
1223 ms |
83880 KB |
Output is correct |
| 4 |
Correct |
1283 ms |
83880 KB |
Output is correct |
| 5 |
Correct |
819 ms |
83880 KB |
Output is correct |
| 6 |
Correct |
303 ms |
71592 KB |
Output is correct |
| 7 |
Correct |
1253 ms |
83880 KB |
Output is correct |
| 8 |
Correct |
476 ms |
83880 KB |
Output is correct |
| 9 |
Correct |
476 ms |
83880 KB |
Output is correct |
| 10 |
Correct |
703 ms |
83880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
859 ms |
71592 KB |
Output is correct |
| 2 |
Correct |
676 ms |
71592 KB |
Output is correct |
| 3 |
Correct |
566 ms |
71592 KB |
Output is correct |
| 4 |
Correct |
726 ms |
71592 KB |
Output is correct |
| 5 |
Correct |
406 ms |
71592 KB |
Output is correct |
| 6 |
Correct |
716 ms |
71592 KB |
Output is correct |
| 7 |
Correct |
893 ms |
71592 KB |
Output is correct |
| 8 |
Correct |
736 ms |
71592 KB |
Output is correct |
| 9 |
Correct |
689 ms |
71592 KB |
Output is correct |
| 10 |
Correct |
719 ms |
71592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1616 ms |
83880 KB |
Output is correct |
| 2 |
Correct |
886 ms |
83880 KB |
Output is correct |
| 3 |
Correct |
1473 ms |
83880 KB |
Output is correct |
| 4 |
Correct |
426 ms |
71592 KB |
Output is correct |
| 5 |
Correct |
1509 ms |
83880 KB |
Output is correct |
| 6 |
Correct |
506 ms |
71592 KB |
Output is correct |
| 7 |
Correct |
1409 ms |
83880 KB |
Output is correct |
| 8 |
Correct |
1766 ms |
83880 KB |
Output is correct |
| 9 |
Correct |
966 ms |
83880 KB |
Output is correct |
| 10 |
Correct |
966 ms |
83880 KB |
Output is correct |
| 11 |
Correct |
753 ms |
71592 KB |
Output is correct |
