灰名飞舞看不了样例,求调 错了subtask0的task9,subtask1全对
#include<bits/stdc++.h>
using namespace std;
struct airport
{
int st,ed;
friend bool operator < (airport z1,airport z2)
{
return z1.st<z2.st;
}
} a[110005],b[110005];
struct node
{
int ed,bg;
};
node init;
int n,m1,m2,itm,ans;
int usein[110005],useout[110005];
priority_queue<int , vector<int> , greater<int> > bge;//bridge
node stk[110007];//不会写struct的priority_queue
void solve1(int plc)
{
if(plc==1) return;
if(stk[plc/2].ed>stk[plc].ed)
{
swap(stk[plc/2],stk[plc]);
solve1(plc/2);
}
}
void solve2(int plc)
{
if(stk[plc*2].ed==0) return;
if(stk[plc*2+1].ed==0)
{
if(stk[plc*2].ed<stk[plc].ed)
{
swap(stk[plc*2],stk[plc]);
}
return;
}
int cse = stk[plc*2].ed<stk[plc*2+1].ed?plc*2:plc*2+1;
if(stk[plc].ed<stk[cse].ed) return;
swap(stk[plc],stk[cse]);
solve2(cse);
return;
}
//usein[i]国内第i个廊桥有几个飞机驶入,后做前缀和变成用i个廊桥能进入几个
//useout类似
int main()
{
init.ed=0;init.bg=0;
scanf("%d%d%d",&n,&m1,&m2);
for(int i = 1;i<=m1;i++) scanf("%d%d",&a[i].st,&a[i].ed);
for(int i = 1;i<=m2;i++) scanf("%d%d",&b[i].st,&b[i].ed);
sort(a+1,a+m1+1);
sort(b+1,b+m2+1);
int cm=1;
itm = 0;
for(int i = 1;i<=100005;i++) bge.push(i);
while(cm<=m1)
{
if( itm==0 || stk[1].ed > a[cm].st)
{
usein[bge.top()] ++;
node ld;
ld.bg = bge.top();
ld.ed = a[cm].ed;
stk[++itm] = ld;
solve1(itm);
bge.pop();
cm++;
}
else
{
bge.push(stk[1].bg);
stk[1] = stk[itm];
stk[itm] = init;
itm--;
solve2(1);
}
}
while(! bge.empty()) bge.pop();
for(int i = 0;i<=100005;i++) stk[i] = init;
cm=1;itm=0;
for(int i = 1;i<=100005;i++) bge.push(i);
while(cm<=m2)
{
if( itm==0 || stk[1].ed > b[cm].st)
{
useout[bge.top()] ++;
node ld;
ld.bg = bge.top();
ld.ed = b[cm].ed;
stk[++itm] = ld;
solve1(itm);
bge.pop();
cm++;
}
else
{
bge.push(stk[1].bg);
stk[1] = stk[itm];
stk[itm] = init;
itm--;
solve2(1);
}
}
for(int i = 1;i<=m1;i++) usein[i] += usein[i-1];
for(int i = 1;i<=m2;i++) useout[i] += useout[i-1];
for(int i = 0;i<=n;i++)
{
ans = max(ans,usein[i]+useout[n-i]);
}
cout<<ans;
return 0;
}