#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 6e5;
struct Data
{
int la, ra, lb, rb; ll w; int chk;
bool operator < (const Data &p) const
{
if(w!=p.w) return w<p.w;
if(chk!=p.chk) return chk>p.chk;
if(chk==1) return la>p.la;
else return lb>p.lb;
}
};
int N, A, B, C;
Data P[MAXN+10];
bool visA[MAXN+10], visB[MAXN+10];
priority_queue<Data> PQ;
struct SEG
{
vector<int> tree[MAXN*4+10];
void update(int node, int tl, int tr, int l, int r, int p)
{
if(r<tl || tr<l) return;
if(l<=tl && tr<=r)
{
tree[node].push_back(p);
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, p);
update(node*2+1, mid+1, tr, l, r, p);
}
void query(int node, int tl, int tr, int p)
{
for(auto it : tree[node])
{
if(P[it].chk!=0) continue;
P[it].chk=1;
PQ.push(P[it]);
//printf("!%d\n", it);
}
vector<int>().swap(tree[node]);
if(tl==tr) return;
int mid=tl+tr>>1;
if(p<=mid) query(node*2, tl, mid, p);
else query(node*2+1, mid+1, tr, p);
}
}seg;
int par[MAXN+10];
int Find(int x)
{
if(x==par[x]) return x;
return par[x]=Find(par[x]);
}
ll ans=0;
int main()
{
scanf("%d%d%d%d", &A, &B, &C, &N);
vector<int> comp;
comp.push_back(C);
comp.push_back(C+1);
for(int i=1; i<=N; i++)
{
scanf("%d%d%d%d%lld", &P[i].la, &P[i].ra, &P[i].lb, &P[i].rb, &P[i].w);
P[i].lb+=A; P[i].rb+=A;
P[i].ra++; P[i].rb++;
P[i].chk=0;
comp.push_back(P[i].la);
comp.push_back(P[i].la+1);
comp.push_back(P[i].ra);
comp.push_back(P[i].lb);
comp.push_back(P[i].lb+1);
comp.push_back(P[i].rb);
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
for(int i=1; i<=N; i++)
{
P[i].la=lower_bound(comp.begin(), comp.end(), P[i].la)-comp.begin()+1;
P[i].lb=lower_bound(comp.begin(), comp.end(), P[i].lb)-comp.begin()+1;
P[i].ra=lower_bound(comp.begin(), comp.end(), P[i].ra)-comp.begin()+1;
P[i].rb=lower_bound(comp.begin(), comp.end(), P[i].rb)-comp.begin()+1;
seg.update(1, 1, comp.size()-1, P[i].la, P[i].ra-1, i);
seg.update(1, 1, comp.size()-1, P[i].lb, P[i].rb-1, i);
}
for(int i=1; i<=comp.size()+1; i++) par[i]=i;
int now=lower_bound(comp.begin(), comp.end(), C)-comp.begin()+1; ll cnt=0, bef=0;
while(1)
{
ans+=bef*(comp[now]-comp[now-1]);
cnt+=comp[now]-comp[now-1];
seg.query(1, 1, comp.size()-1, now);
par[now]=now+1;
Data p; bool t=false;
while(!PQ.empty())
{
p=PQ.top();
if(p.chk==2)
{
if(Find(p.lb)>=p.rb) { PQ.pop(); continue; }
t=true; break;
}
if(p.chk==1)
{
if(Find(p.la)>=p.ra)
{
p.chk=2;
PQ.pop();
PQ.push(p);
continue;
}
t=true; break;
}
}
if(!t) break;
bef=p.w;
//printf("%d %d %d %d %lld\n", p.la, p.ra, p.lb, p.rb, p.w);
if(p.chk==1)
{
now=Find(p.la);
}
else
{
now=Find(p.lb);
}
}
if(cnt==A+B) printf("%lld\n", ans);
else printf("-1\n");
}
Compilation message
invitation.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
invitation.cpp:40:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid=tl+tr>>1;
| ~~^~~
invitation.cpp: In member function 'void SEG::query(int, int, int, int)':
invitation.cpp:56:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | int mid=tl+tr>>1;
| ~~^~~
invitation.cpp: In function 'int main()':
invitation.cpp:108:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=1; i<=comp.size()+1; i++) par[i]=i;
| ~^~~~~~~~~~~~~~~
invitation.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
73 | scanf("%d%d%d%d", &A, &B, &C, &N);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
invitation.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
80 | scanf("%d%d%d%d%lld", &P[i].la, &P[i].ra, &P[i].lb, &P[i].rb, &P[i].w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
56704 KB |
Output is correct |
| 2 |
Correct |
41 ms |
56704 KB |
Output is correct |
| 3 |
Correct |
38 ms |
56704 KB |
Output is correct |
| 4 |
Correct |
40 ms |
56832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
56696 KB |
Output is correct |
| 2 |
Correct |
39 ms |
56728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
57248 KB |
Output is correct |
| 2 |
Correct |
43 ms |
57088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
57464 KB |
Output is correct |
| 2 |
Correct |
48 ms |
57592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
57464 KB |
Output is correct |
| 2 |
Correct |
46 ms |
57592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1039 ms |
102876 KB |
Output is correct |
| 2 |
Correct |
270 ms |
72196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1134 ms |
102432 KB |
Output is correct |
| 2 |
Correct |
557 ms |
107484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1069 ms |
103004 KB |
Output is correct |
| 2 |
Correct |
260 ms |
72132 KB |
Output is correct |
| 3 |
Correct |
775 ms |
88156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1047 ms |
98312 KB |
Output is correct |
| 2 |
Correct |
562 ms |
107612 KB |
Output is correct |
| 3 |
Correct |
687 ms |
85724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
70364 KB |
Output is correct |
| 2 |
Correct |
931 ms |
95708 KB |
Output is correct |
| 3 |
Correct |
1046 ms |
102748 KB |
Output is correct |
