#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 maxn = 2e5;
const long long maxsz = maxn * 4;
long long n,m,c,x[maxn],y[maxn],p[maxn],q[maxn],r[maxn],s[maxn],Truex[maxsz],Truey[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;
struct T_node
{
int l,r,val,lazy;
} node[maxsz*6];
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 Build_tree(int i, int l, int r)
{
node[i].l = l;
node[i].r = r;
node[i].val = 0;
node[i].lazy = 0;
if (l != r) {
Build_tree(i*2,l,(l+r)/2);
Build_tree(i*2+1,(l+r)/2+1,r);
}
}
void Down_node(int i)
{
node[i].val += node[i].lazy;
if (node[i].l != node[i].r) {
node[i*2].lazy += node[i].lazy;
node[i*2+1].lazy += node[i].lazy;
}
node[i].lazy = 0;
}
void Recal(int i)
{
Down_node(i*2);
Down_node(i*2+1);
node[i].val = max(node[i*2].val,node[i*2+1].val);
}
void Update(int i, int l, int r, int d)
{
if (r < node[i].l || node[i].r < l)
return;
if (l <= node[i].l && node[i].r <= r)
node[i].lazy += d;
else {
Down_node(i);
Update(i*2,l,r,d);
Update(i*2+1,l,r,d);
Recal(i);
}
}
int Query(int i, int l, int r)
{
if (r < node[i].l || node[i].r < l)
return 0;
Down_node(i);
if (l <= node[i].l && node[i].r <= r)
return node[i].val;
else {
int res = max(Query(i*2,l,r),Query(i*2+1,l,r));
Recal(i);
return res;
}
}
void BuildGraph()
{
Build_tree(1,1,maxsz);
for (long long Y=1;Y<maxsz;++Y) {
add[Y].clear();
sub[Y].clear();
mem[Y].clear();
}
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])
Update(1,p[i],r[i],+1);
for (long long i : sub[Y])
Update(1,p[i],r[i],-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 (Query(1,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 = 1;
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;
}
l = max(l-1,n2-h);
cout << chose[l] + 1ll * b * (n - l) << '\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:141: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 |
192 ms |
112252 KB |
Output is correct |
| 2 |
Incorrect |
629 ms |
123160 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2476 ms |
141436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
622 ms |
141436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2415 ms |
141436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
