#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e6 + 5e5 + 9;
const ll inf = 1e9 + 7;
vector<ll> V;
struct city{
ll x,y,id;
};
city a[N];
struct rect{
ll x,y,u,v;
};
rect r[N];
ll n,m,Q,x,y,u,v,pre[N],cc,was[N],price,cnt;
bool lf1(city a,city b){
return a.x < b.x;
}
bool lf2(city a,city b){
return a.y < b.y;
}
bool cmp1(ll x,ll y){
return a[x].y < a[y].y;
}
bool cmp2(ll x,ll y){
return a[x].x < a[y].x;
}
vector<ll> g[N],point[2][N];
struct seg{
ll l,r,val;
};
vector<seg> pos[2][N];
ll st[4*N],lazy[4*N],total;
ll Find(ll x){
return lower_bound(V.begin(),V.end(),x) - V.begin() + 1;
}
void compress(){
sort(V.begin(),V.end()); V.resize(unique(V.begin(),V.end()) - V.begin());
for (ll i = 1;i <= n;i++){
a[i].x = Find(a[i].x),a[i].y = Find(a[i].y);
x = a[i].x; y = a[i].y;
point[0][x].push_back(i); point[1][y].push_back(i);
}
for (ll i = 1;i <= m;i++){
r[i].x = Find(r[i].x),r[i].y = Find(r[i].y),r[i].u = Find(r[i].u),r[i].v = Find(r[i].v);
x = r[i].x; y = r[i].y; u = r[i].u; v = r[i].v;
pos[0][x].push_back({y,v,1}); pos[0][u].push_back({y,v,-1});
pos[1][y].push_back({x,u,1}); pos[1][v].push_back({x,u,-1});
}
}
map<LL,ll> mp;
void Pass(ll id){
ll t = lazy[id]; lazy[id] = 0;
st[id*2] += t; lazy[id*2] += t;
st[id*2 + 1] += t; lazy[id*2 + 1] += t;
}
void upd(ll id,ll l,ll r,ll u,ll v,ll val){
if (v < l||r < u) return;
if (u <= l&&r <= v){
st[id] += val; lazy[id] += val; return;
}
ll mid = (l + r)/2; Pass(id);
upd(id*2,l,mid,u,v,val); upd(id*2 + 1,mid + 1,r,u,v,val);
st[id] = max(st[id*2],st[id*2 + 1]);
}
ll Get(ll id,ll l,ll r,ll u,ll v){
if (v < l||r < u) return 0;
if (u <= l&&r <= v) return st[id];
ll mid = (l + r)/2; Pass(id);
return max(Get(id*2,l,mid,u,v),Get(id*2 + 1,mid + 1,r,u,v));
}
void process(ll cond){
memset(st,0,sizeof(st)); memset(lazy,0,sizeof(lazy));
for (ll i = 1;i < N;i++){
for (auto j : pos[cond][i]) upd(1,1,N - 1,j.l,j.r,j.val);
ll sz = point[cond][i].size();
for (ll j = 1;j < sz;j++){
ll now = point[cond][i][j],prv = point[cond][i][j - 1];
ll L = a[prv].x,R = a[now].x;
if (!cond) L = a[prv].y,R = a[now].y;
if (Get(1,1,N - 1,L,R)) mp[{now,prv}] = mp[{prv,now}] = 1;
}
}
}
struct Edge{
ll u,v,val;
};
bool fuck(Edge x,Edge y){
return x.val < y.val;
}
vector<Edge> e,chosen;
void build_graph(ll cond){
if (!cond) sort(a + 1,a + n + 1,lf1);
else sort(a + 1,a + n + 1,lf2);
for (ll i = 1;i < n;i++){
if (a[i].x == a[i + 1].x||a[i].y == a[i + 1].y){
ll p = a[i].id,q = a[i + 1].id;
ll rx = V[a[i].x - 1],ry = V[a[i].y - 1],rx1 = V[a[i + 1].x - 1],ry1 = V[a[i + 1].y - 1];
if (!mp[{p,q}]) e.push_back({p,q,abs(rx + ry - rx1 - ry1)});//cout<<rx<<" "<<ry<<" x "<<rx1<<" "<<ry1<<"\n";
}
}
//exit(0);
}
ll lab[N];
ll Find_lab(ll u){
if (lab[u] < 0) return u;
return lab[u] = Find_lab(lab[u]);
}
void Union(ll r,ll s){
if (lab[r] > lab[s]) swap(r,s);
lab[r] += lab[s]; lab[s] = r;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n>>m>>Q;
for (ll i = 1;i <= n;i++) cin>>a[i].x>>a[i].y,a[i].id = i,V.push_back(a[i].x),V.push_back(a[i].y);
for (ll i = 1;i <= m;i++){
cin>>r[i].x>>r[i].y>>r[i].u>>r[i].v;
V.push_back(r[i].x); V.push_back(r[i].y); V.push_back(r[i].u); V.push_back(r[i].v);
}
compress(); memset(lab,-1,sizeof(lab));
for (ll i = 1;i < N - 3;i++)
sort(point[0][i].begin(),point[0][i].end(),cmp1),sort(point[1][i].begin(),point[1][i].end(),cmp2); //return 0;
process(0); process(1); build_graph(0); build_graph(1); sort(e.begin(),e.end(),fuck);
//for (auto i : e) cout<<i.u<<" "<<i.v<<" "<<i.val<<"\n";
for (auto i : e){
ll r = Find_lab(i.u),s = Find_lab(i.v);
if (r != s) Union(r,s),total += i.val,chosen.push_back(i);
}
reverse(chosen.begin(),chosen.end());
pre[0] = chosen[0].val;
for (ll i = 1;i < chosen.size();i++) pre[i] = pre[i - 1] + chosen[i].val;
for (ll i = 1;i <= n;i++){
ll now = Find_lab(i);
if (!was[now]) cc++; was[now] = 1;
}
while(Q--){
ll inc = 0;
cin>>price>>cnt; cnt -= cc;
if (cnt < 0){
cout<<"-1\n"; continue;
}
ll l,mid,h; l = 0; h = chosen.size() - 1;
while(l <= h){
mid = (l + h)/2;
if (chosen[mid].val < price) h = mid - 1;
else l = mid + 1;
}
//cout<<h; return 0;
ll p = min(cnt - 1,h);
if (p >= 0) inc = pre[p] - (p + 1)*price;
cout<<total - inc + cc*price<<"\n";
}
}
Compilation message
construction.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
construction.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
construction.cpp: In function 'int main()':
construction.cpp:162:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for (ll i = 1;i < chosen.size();i++) pre[i] = pre[i - 1] + chosen[i].val;
| ~~^~~~~~~~~~~~~~~
construction.cpp:165:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
165 | if (!was[now]) cc++; was[now] = 1;
| ^~
construction.cpp:165:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
165 | if (!was[now]) cc++; was[now] = 1;
| ^~~
construction.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
142 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
209 ms |
231788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
209 ms |
231788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
209 ms |
231788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
209 ms |
231788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
