#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()));
}
typedef long long ll;
const int N = 2e5+111;
int n, m, k, pos[3*N], num, cnt, D[3*N], ID[3*N], Fa[N];
ll RD[3*N], F[N];
vector<pair<ll,int> > Adj[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;
}
} A[N], P[3*N];
struct rect{
pt up, down;
rect(){}
rect(pt a, pt b){
up = a; down = b;
}
} B[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, ll g){
x = a; y = b; l = c; r = d; type = e; id = f; rx = g;
}
};
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;
}
for(int i = 1; i <= n; i++){
A[i] = P[i];
}
for(int i = 1; i < 2*m; i+=2){
B[i/2+1] = rect(P[i+n],P[i+n+1]);
}
}
struct SegTree{
int ST[12*N], Lazy[12*N];
void reset(){
memset(ST,0,sizeof(ST));
memset(Lazy,0,sizeof(Lazy));
}
void down(int id, int l, int r){
if(!Lazy[id]) 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] = 0;
}
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;
RD[dt.y] = dt.rx;
}
else{
int x = Tree.get(1,1,num,dt.y);
int id = ID[dt.y];
ll xx = RD[dt.y];
if(D[dt.y]>x){
Adj[dt.id].push_back(mp((ll)abs(xx-dt.rx),id));
Adj[id].push_back(mp((ll)abs(xx-dt.rx),dt.id));
}
D[dt.y] = dt.x;
RD[dt.y] = dt.rx;
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){
read(P[n+i].x); read(P[n+i].y);
read(P[n+i+1].x); read(P[n+i+1].y);
}
compress();
for(int i = 1; i <= n; i++){
T.push_back(data(A[i].x,A[i].y,0,0,1,i,A[i].rx));
}
for(int i = 1; i <= m; i++){
T.push_back(data(B[i].up.x,0,B[i].up.y,B[i].down.y,0,0,0));
T.push_back(data(B[i].down.x,0,B[i].up.y,B[i].down.y,0,0,0));
}
makeGraph();
T.clear();
for(int i = 1; i <= n; i++){
T.push_back(data(A[i].y,A[i].x,0,0,1,i,A[i].ry));
}
for(int i = 1; i <= m; i++){
T.push_back(data(B[i].up.y,0,B[i].up.x,B[i].down.x,0,0,0));
T.push_back(data(B[i].down.y,0,B[i].up.x,B[i].down.x,0,0,0));
}
makeGraph();
int eNum = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j < (int)Adj[i].size(); j++){
E[++eNum] = Edge(i,Adj[i][j].Y,Adj[i][j].X);
}
}
sort(E+1,E+eNum+1);
memset(Fa,255,sizeof(Fa));
int com = n;
ll sum = 0;
vector<ll> edge;
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;
edge.push_back(w);
}
for(int i = edge.size()-1; i >= 0; i--){
F[i] = F[i+1]+edge[i];
}
while(k--){
ll c;
int h;
read(c); read(h);
if(h<com) cout<<-1<<endl;
else if(edge.empty()){
ll res = c*(ll)n;
cout<<res<<endl;
}
else if(c>=edge.back()){
ll res = F[0]+c*(ll)com;
cout<<res<<endl;
}
else{
int p = upper_bound(edge.begin(),edge.end(),c)-edge.begin();
int tt = max(p,((int)edge.size()-(h-com)));
ll res = c*(ll)(com+(int)edge.size()-tt)+sum-F[tt];
cout<<res<<endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
81180 KB |
Output is correct |
| 2 |
Correct |
366 ms |
95864 KB |
Output is correct |
| 3 |
Correct |
359 ms |
95968 KB |
Output is correct |
| 4 |
Correct |
533 ms |
110548 KB |
Output is correct |
| 5 |
Correct |
526 ms |
102800 KB |
Output is correct |
| 6 |
Correct |
329 ms |
96248 KB |
Output is correct |
| 7 |
Correct |
369 ms |
110644 KB |
Output is correct |
| 8 |
Correct |
266 ms |
102068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1569 ms |
129564 KB |
Output is correct |
| 2 |
Correct |
1703 ms |
129564 KB |
Output is correct |
| 3 |
Correct |
1589 ms |
129564 KB |
Output is correct |
| 4 |
Correct |
1619 ms |
129564 KB |
Output is correct |
| 5 |
Correct |
1066 ms |
129564 KB |
Output is correct |
| 6 |
Correct |
546 ms |
102820 KB |
Output is correct |
| 7 |
Correct |
1576 ms |
129564 KB |
Output is correct |
| 8 |
Correct |
803 ms |
135220 KB |
Output is correct |
| 9 |
Correct |
773 ms |
135220 KB |
Output is correct |
| 10 |
Correct |
1026 ms |
129564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
826 ms |
96284 KB |
Execution timed out (wall clock limit exceeded) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2209 ms |
129564 KB |
Execution timed out (wall clock limit exceeded) |
| 2 |
Halted |
0 ms |
0 KB |
- |
