#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 2000001;
int n,m,q,xx[MAXN],yy[MAXN];
struct rect{
int y1,x1,y2,x2;
void read(){ cin>>y1>>x1>>y2>>x2; }
void rotate(){ swap(x1,y1); swap(x2,y2); }
}r[MAXN];
vector<pair<int,int> > event;
struct segTree{
vector<int> lazy,tree,comp;
int lb(int x){ return lower_bound(comp.begin(),comp.end(),x) - comp.begin() + 1; }
void in(int x){ comp.push_back(x);}
void clear(){ lazy.clear(); tree.clear(); comp.clear();}
void set(){
sort(comp.begin(),comp.end());
comp.erase(unique(comp.begin(),comp.end()),comp.end());
tree.resize(comp.size() * 4 + 4, 0);
lazy.resize(comp.size() * 4 + 4, -1);
}
void push(int node,int st,int ed){
if(lazy[node] == -1)return;
tree[node] = lazy[node];
if(st != ed){
lazy[2 * node] = lazy[node];
lazy[2 * node + 1] = lazy[node];
}
lazy[node] = -1;
}
void update(int node,int st,int ed,int l,int r,int val){
push(node,st,ed);
if(st > r || ed < l)return;
if(st >= l && ed <= r){
lazy[node] = val;
push(node,st,ed);
return;
}
update(node*2,st,(st+ed)/2,l,r,val);
update(node*2+1,(st+ed)/2+1,ed,l,r,val);
tree[node] = max(tree[node*2],tree[node*2+1]);
}
int query(int node,int st,int ed,int l,int r){
push(node,st,ed);
if(st > r || ed < l) return -1e9;
if(st >= l && ed <= r)return tree[node];
auto L = query(node*2,st,(st+ed)/2,l,r);
auto R = query(node*2+1,(st+ed)/2+1,ed,l,r);
return max(L,R);
}
int query(int l,int r){
l = lb(l); r = lb(r);
return query(1,1,comp.size(),l,r);
}
void update(int l,int r,int val){
l = lb(l); r = lb(r);
update(1,1,comp.size(),l,r,val);
}
}ft;
vector<pair<int,int> > vc[MAXN];
struct info{
int x,type,idx;
bool operator < (const info in)const{
if(x != in.x)return x < in.x;
if(type != in.type) return type < in.type;
return idx < in.idx;
}
};
struct edge{
int u,v,w;
bool operator < (const edge e)const{
return w < e.w;
}
};
vector<edge> e;
void solve(){
vector<info> event;
ft.clear();
for(int i = 0; i < MAXN; i++) vc[i].clear();
for(int i = 1; i <= n; i++) ft.in(yy[i]);
for(int i = 1; i <= m; i++) { ft.in(r[i].y1); ft.in(r[i].y2); }
ft.set();
for(int i = 1; i <= n; i++){
event.push_back({xx[i],1,i});
}
for(int i = 1; i <= m; i++){
event.push_back({r[i].x1,0,i});
event.push_back({r[i].x2,2,i});
}
sort(event.begin(),event.end());
for(int i = 0; i < event.size(); i++){
int type = event[i].type;
int idx = event[i].idx;
if(type == 0){ //line open
ft.update(r[idx].y1,r[idx].y2,r[idx].x1);
}
else if(type == 1){ //dot
int loc = ft.lb(yy[idx]);
if(vc[loc].size()){
int last = vc[loc].back().second;
if(ft.query(yy[last],yy[last]) < xx[last]){
e.push_back({last,idx,abs(xx[idx]-xx[last])});
}
}
vc[loc].push_back(make_pair(xx[idx],idx));
}
else{
ft.update(r[idx].y1,r[idx].y2,r[idx].x2);
}
}
for(int i = 1; i <= n; i++) swap(xx[i],yy[i]);
for(int i = 1; i <= m; i++) r[i].rotate();
}
int parent[MAXN];
int find(int u){
return u == parent[u] ? u : parent[u] = find(parent[u]);
}
void mrg(int u,int v){
u = find(u);
v = find(v);
if(u == v)return;
parent[u] = v;
}
long long cost[MAXN];
int tot;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m >> q;
for(int i = 1; i <= n; i++){
cin >> yy[i] >> xx[i];
}
for(int i = 1; i <= m; i++){
r[i].read();
}
solve();
solve();
for(int i = 0; i < MAXN; i++) parent[i] = i;
sort(e.begin(),e.end());
for(int i = 1; i < MAXN; i++)cost[i] = 3e18;
int piv = 0;
vector<pair<int,int> > use;
tot = n;
use.push_back(make_pair(0,0));
vector<pair<int,int> > vc;
for(auto x:e){
int u = x.u; int v = x.v; int w = x.w;
vc.push_back(make_pair(min(u,v),max(u,v)));
if(find(u) == find(v)) continue;
mrg(u,v);
tot--;
++piv; cost[piv] = cost[piv-1] + w;
use.push_back(make_pair(piv,w));
}
//sort(vc.begin(),vc.end());
//for(auto x:vc)cout<<x.first<<' '<<x.second<<endl;
for(int i = 1; i <= q; i++){
long long b,h;
cin >> b >> h;
//컴포넌트를 n 개로 만들려면 엣지를 하나도 연결 안하면됨
if(h < tot) { cout<<-1<<"\n"; continue; }
long long lo = n - h; long long hi = use.size() - 1; //euse
lo = max(lo,0LL);
int euse = lo;
while(lo <= hi){
int mid = (lo+hi)/2;
if(use[mid].second < b){
lo = mid + 1;
euse = mid;
}
else hi = mid - 1;
}
long long ans = cost[euse] + 1LL * (n-euse) * b;
cout<<ans<<"\n";
}
return 0;
}
Compilation message
construction.cpp: In function 'void solve()':
construction.cpp:110:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < event.size(); i++){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
71792 KB |
Output is correct |
| 2 |
Correct |
562 ms |
86808 KB |
Output is correct |
| 3 |
Correct |
601 ms |
90504 KB |
Output is correct |
| 4 |
Incorrect |
496 ms |
96788 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2398 ms |
122804 KB |
Output is correct |
| 2 |
Correct |
2409 ms |
122952 KB |
Output is correct |
| 3 |
Correct |
2476 ms |
122952 KB |
Output is correct |
| 4 |
Correct |
2446 ms |
122952 KB |
Output is correct |
| 5 |
Incorrect |
1303 ms |
122952 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
787 ms |
122952 KB |
Output is correct |
| 2 |
Correct |
793 ms |
122952 KB |
Output is correct |
| 3 |
Correct |
811 ms |
122952 KB |
Output is correct |
| 4 |
Incorrect |
704 ms |
122952 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2557 ms |
149136 KB |
Output is correct |
| 2 |
Correct |
1608 ms |
149136 KB |
Output is correct |
| 3 |
Correct |
2606 ms |
162536 KB |
Output is correct |
| 4 |
Correct |
754 ms |
162536 KB |
Output is correct |
| 5 |
Correct |
2520 ms |
193408 KB |
Output is correct |
| 6 |
Correct |
782 ms |
193408 KB |
Output is correct |
| 7 |
Correct |
2381 ms |
230644 KB |
Output is correct |
| 8 |
Correct |
2671 ms |
249164 KB |
Output is correct |
| 9 |
Correct |
934 ms |
249164 KB |
Output is correct |
| 10 |
Correct |
1267 ms |
262144 KB |
Output is correct |
| 11 |
Correct |
643 ms |
262144 KB |
Output is correct |
