#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);
cin>>n>>m>>k;
for(int i = 1; i <= n; i++){
int x, y;
//read(x); read(y);
cin>>x>>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);
cin>>P[n+i].x>>P[n+i].y>>P[n+i+1].x>>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;
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);
cin>>c>>h;
if(h<com) cout<<-1<<endl;
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;
cout<<res<<endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
81176 KB |
Output is correct |
| 2 |
Correct |
366 ms |
93744 KB |
Output is correct |
| 3 |
Correct |
406 ms |
93876 KB |
Output is correct |
| 4 |
Correct |
576 ms |
106416 KB |
Output is correct |
| 5 |
Correct |
523 ms |
98628 KB |
Output is correct |
| 6 |
Correct |
399 ms |
94140 KB |
Output is correct |
| 7 |
Correct |
426 ms |
106416 KB |
Output is correct |
| 8 |
Correct |
293 ms |
97968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1699 ms |
129560 KB |
Output is correct |
| 2 |
Correct |
1653 ms |
129560 KB |
Output is correct |
| 3 |
Correct |
1756 ms |
129560 KB |
Output is correct |
| 4 |
Correct |
1753 ms |
129560 KB |
Output is correct |
| 5 |
Correct |
1096 ms |
129560 KB |
Output is correct |
| 6 |
Correct |
386 ms |
98628 KB |
Output is correct |
| 7 |
Correct |
1656 ms |
129560 KB |
Output is correct |
| 8 |
Correct |
786 ms |
130992 KB |
Output is correct |
| 9 |
Correct |
819 ms |
130992 KB |
Output is correct |
| 10 |
Correct |
979 ms |
129560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
913 ms |
94140 KB |
Execution timed out (wall clock limit exceeded) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
0 KB |
-1: Interrupted system call
|
| 2 |
Halted |
0 ms |
0 KB |
- |
