#define Link "https://dunjudge.me/analysis/problems/980/?fbclid=IwAR0lz5NJ1ferKp5nADDwgoLiHvUbIE48RZqI5DtvPEqUlf-6RFpMV2Thm_c"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define TASK "Construction Project"
using namespace std;
const long long maxsz = 2e5 * 4;
const long long maxn = 2e5;
long long n,m,c,x[maxn],y[maxn],p[maxn],q[maxn],r[maxn],s[maxn],Truex[maxsz],Truey[maxsz];
long long node[maxsz];
vector <long long> add[maxsz],sub[maxsz],mem[maxsz];
long long cntedge,u[maxsz],v[maxsz],w[maxsz],id[maxsz];
long long lab[maxsz];
vector <long long> chose;
void Enter()
{
cin >> n >> m >> c;
for (long long i=1;i<=n;++i)
cin >> x[i] >> y[i];
for (long long i=1;i<=m;++i)
cin >> p[i] >> q[i] >> r[i] >> s[i];
}
void Analyze(long long a[], long long b[], long long c[], long long True[])
{
vector <long long*> v;
for (long long i=1;i<=n;++i)
v.push_back(&a[i]);
for (long long i=1;i<=m;++i)
v.push_back(&b[i]);
for (long long i=1;i<=m;++i)
v.push_back(&c[i]);
sort(v.begin(),v.end(),
[] (long long *i, long long *j)
{
return *i < *j;
});
long long cnt = 0;
long long pre = -1;
for (auto p : v) {
if (*p != pre) {
++cnt;
// cout << *p << ' ';
True[cnt] = pre = *p;
}
*p = cnt;
}
// cout << '\n' << '\n';;
}
void Update(long long i, long long d)
{
for (;i<maxsz;i+=i&-i) {
node[i] += d;
// cout << i << ' ' << node[i] << " " ;
}
// cout << '\n';
}
long long Query(long long i)
{
long long res = 0;
// cout << i << '\n';
for (;i>0;i&=(i-1)) {
res += node[i];
// cout << i << ' ' << node[i] << " " ;
}
// cout << '\n';
return res;
}
long long QuerySum(long long l, long long r)
{
// cout << l << ' ' << r << ' ' << Query(r) << ' ' << Query(l-1) << '\n';
return Query(r) - Query(l-1);
}
void BuildGraph()
{
for (long long Y=1;Y<maxsz;++Y) {
add[Y].clear();
sub[Y].clear();
mem[Y].clear();
}
fill(node,node+maxsz,0);
for (long long i=1;i<=m;++i) {
add[q[i]].push_back(i);
sub[s[i]+1].push_back(i);
}
for (long long i=1;i<=n;++i)
mem[y[i]].push_back(i);
for (long long Y=1;Y<maxsz;++Y) {
for (long long i : add[Y]) {
// cout << p[i] << ' ' << r[i] << " +1" << '\n';
Update(p[i],+1);
// Update(r[i]+1,-1);
}
for (long long i : sub[Y]) {
// cout << p[i] << ' ' << r[i] << " -1" << '\n';
Update(p[i],-1);
// Update(r[i]+1,+1);
}
sort(mem[Y].begin(),mem[Y].end(),
[] (long long i, long long j)
{
return x[i] < x[j];
});
for (long long t=0;t+1<mem[Y].size();++t) {
long long i1 = mem[Y][t];
long long i2 = mem[Y][t+1];
// cout << i1 << ' ' << i2 << ' ' << x[i1] << ' ' << x[i2] << ' ' << Truex[x[i1]] << ' ' << Truex[x[i2]] << ' ' << QuerySum(x[i1],x[i2]) << '\n';
if (QuerySum(x[i1],x[i2]) == 0) {
++cntedge;
u[cntedge] = i1;
v[cntedge] = i2;
w[cntedge] = Truex[x[i2]] - Truex[x[i1]];
}
}
}
}
void Init()
{
Analyze(x,p,r,Truex);
Analyze(y,q,s,Truey);
BuildGraph();
swap(x,y);
swap(q,p);
swap(r,s);
swap(Truex,Truey);
BuildGraph();
swap(x,y);
swap(q,p);
swap(r,s);
swap(Truex,Truey);
}
long long Find_set(long long n)
{
return lab[n] > 0 ? lab[n] = Find_set(lab[n]) : n;
}
bool Union(long long s, long long t)
{
if (s == t)
return 0;
if (lab[s] > lab[t])
swap(s,t);
lab[s] += lab[t];
lab[t] = s;
return 1;
}
void Solve()
{
for (long long i=1;i<=cntedge;++i)
id[i] = i;
sort(id+1,id+cntedge+1,
[] (long long i, long long j)
{
return w[i] < w[j];
});
for (long long t=1;t<=cntedge;++t) {
long long i = id[t];
if (Union(Find_set(u[i]),Find_set(v[i]))) {
// cout << u[i] << ' ' << v[i] << ' ' << w[i] << '\n';
chose.push_back(w[i]);
}
}
long long n2 = chose.size();
chose.push_back(0);
sort(chose.begin(),chose.end());
for (long long i=1;i<=n2;++i)
chose[i] += chose[i-1];
for (long long i=1;i<=c;++i) {
long long b,h;
cin >> b >> h;
// cout << b << ' ' << h << ' ' << n << ' ' << n2 << '\n';
h -= n - n2;
if (h >= 0) {
long long l = max(n2 - h, 1ll);
long long r = n2;
while (l <= r) {
long long m = (l + r) / 2;
if (chose[m] - chose[m-1] <= b)
l = m + 1;
else
r = m - 1;
}
cout << chose[r] + 1ll * b * (n - r) << '\n';
}
else
cout << -1 << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef LHL
freopen(".INP","r",stdin);
freopen(".OUT","w",stdout);
#else
// freopen(TASK".INP","r",stdin);
// freopen(TASK".OUT","w",stdout);
#endif // LHL
Enter();
Init();
Solve();
}
Compilation message
construction.cpp: In function 'void BuildGraph()':
construction.cpp:114:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (long long t=0;t+1<mem[Y].size();++t) {
~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
85784 KB |
Output is correct |
| 2 |
Incorrect |
371 ms |
100376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1064 ms |
118752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
376 ms |
118752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1035 ms |
118752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
