#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn =1e6+10;
const ll mod=1e9+7;
const ll base=1e8;
ll a[maxn][2];
map<ll,vector<pll>> mp[2];
ll len[2];
ll st[4*maxn][2];
ll la[4*maxn][2];
void dosth(ll id,ll left,ll right,ll t)
{
if (left==right||la[id][t]==0) return ;
ll mid=(left+right)/2;
st[id*2][t]+=la[id][t]*(mid-left+1);
la[id*2][t]+=la[id][t];
st[id*2+1][t]+=la[id][t]*(right-mid);
la[id*2+1][t]+=la[id][t];
la[id][t]=0;
}
void update(ll id,ll left,ll right,ll x,ll y,ll diff,ll t)
{
dosth(id,left,right,t);
if (x>right||y<left) return ;
if (x<=left&&y>=right)
{
st[id][t]+=diff*(right-left+1);
la[id][t]+=diff;
dosth(id,left,right,t);
return ;
}
ll mid=(left+right)/2;
update(id*2,left,mid,x,y,diff, t);
update(id*2+1, mid+1, right, x, y, diff,t);
st[id][t]=st[id*2][t]+st[id*2+1][t];
}
ll get(ll id,ll left,ll right,ll x,ll y,ll t)
{
dosth(id,left,right,t);
if (x>right||y<left) return 0;
if (x<=left&&y>=right)return st[id][t];
ll mid=(left+right)/2;
return get(id*2,left,mid,x,y,t)+get(id*2+1, mid+1, right, x, y, t);
}
ll par[maxn];
ll find_par(ll u)
{
if (u==par[u]) return u;
return par[u]=find_par(par[u]);
}
bool dsu(ll x,ll y)
{
x=find_par(x);
y=find_par(y);
if (x==y) return false;
par[x]=y;
return true;
}
ll f[maxn];
ll b[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("test.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
ll n, m, c;
cin>> n>> m>> c;
vector<ll> vt[3];
for (int i=1;i<=n;i++)
{
cin>>a[i][0]>>a[i][1];
for (int j=0;j<=1;j++)
{
mp[j][a[i][j]].pb(make_pair(a[i][1-j],i));
vt[j].pb(a[i][1-j]);
}
}
vector<pair<pll,pll>> even[2];
for (int i=1;i<=m;i++)
{
ll x, y, x1, y1;
cin>> x>> y>>x1 >> y1;
even[0].pb(make_pair(make_pair(x,1),make_pair(y,y1)));
even[0].pb(make_pair(make_pair(x1+1,-1),make_pair(y,y1)));
even[1].pb(make_pair(make_pair(y,1),make_pair(x,x1)));
even[1].pb(make_pair(make_pair(y1+1,-1),make_pair(x,x1)));
vt[0].pb(y);
vt[0].pb(y1);
vt[1].pb(x);
vt[1].pb(x1);
}
for (int t=0;t<=1;t++)
{
sort(vt[t].begin(),vt[t].end());
vt[t].resize(unique(vt[t].begin(),vt[t].end())-vt[t].begin());
}
for (int i=0;i<=1;i++) sort(even[i].begin(),even[i].end());
for (int j=0;j<=1;j++)
{
len[j]=vt[j].size();
}
vector<pair<ll,pll>> ed;
for (int i=0;i<=1;i++)
{
ll idnw=0;
for (auto p:mp[i])
{
ll pos=p.ff;
while (idnw<even[i].size()&&even[i][idnw].ff.ff<=pos)
{
ll x=even[i][idnw].ss.ff;
ll y=even[i][idnw].ss.ss;
x=lower_bound(vt[i].begin(),vt[i].end(),x)-vt[i].begin()+1;
y=lower_bound(vt[i].begin(),vt[i].end(),y)-vt[i].begin()+1;
ll diff=even[i][idnw].ff.ss;
/* if (i==1)
{
cout <<x<<" "<<y<<" "<<idnw<<" "<<even[i][idnw].ss.ff<<" "<<even[i][idnw].ss.ss<<" "<<diff<<endl;
for (auto to:vt[i])
{
cout <<to<<" ";
}
cout <<endl;
}*/
update(1,1,len[i],x,y,diff,i);
idnw++;
}
auto vt1=p.ss;
sort(vt1.begin(),vt1.end());
ll t=i;
// if (i==1) cout <<vt1.size()<<endl;
for (int i=1;i<vt1.size();i++)
{
ll x=vt1[i-1].ff;
ll y=vt1[i].ff;
x=lower_bound(vt[t].begin(),vt[t].end(),x)-vt[t].begin()+1;
y=lower_bound(vt[t].begin(),vt[t].end(),y)-vt[t].begin()+1;
ll h=get(1,1,len[t],x,y,t);
if (!h)
{
ll id1=vt1[i-1].ss;
ll id2=vt1[i].ss;
/*if (t==0)
{
cout <<id1<<" "<<id2<<" "<<x<<" "<<y<<endl;
}*/
ed.pb(make_pair(vt1[i].ff-vt1[i-1].ff,make_pair(id1,id2)));
}
}
}
}
for (int i=1;i<=n;i++)
{
par[i]=i;
}
ll cnt=0;
/*cout <<ed.size()<<endl;
for (auto to:ed)
{
cout <<to.ff<<" "<<to.ss.ff<<" "<<to.ss.ss<<endl;
}*/
for (auto to:ed)
{
ll w=to.ff;
//cout <<to.ss.ff<<" "<<to.ss.ss<<" "<<find_par(to.ss.ff)<<" "<<find_par(to.ss.ss)<<endl;
if(dsu(to.ss.ff,to.ss.ss))
{
cnt++;
b[cnt]=w;
f[cnt]=f[cnt-1]+w;
}
}
for (int i=1;i<=c;i++)
{
ll x, y;
cin>> x>> y;
if (cnt+y<n)
{
cout <<-1<<endl;
}
else
{
ll l=1, h=cnt;
// cout <<l<<" "<<h<<endl;
while (l<=h)
{
ll mid=(l+h)/2;
// cout <<mid<<" "<<b[mid]<<" "<<x<<endl;
if (b[mid]>x) h=mid-1;
else l=mid+1;
}
l=max(l,n-y+1);
ll ans=f[l-1]+(n-l+1)*x;
cout <<ans<<endl;
}
}
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:127:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | while (idnw<even[i].size()&&even[i][idnw].ff.ff<=pos)
| ~~~~^~~~~~~~~~~~~~~
construction.cpp:151:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for (int i=1;i<vt1.size();i++)
| ~^~~~~~~~~~~
construction.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
80 | freopen("test.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
construction.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
81 | freopen("test.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
3344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
3344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
3344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
3344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
