我觉得我的复杂度是 O(m1logm1+m2logm2+n) 的,喜提40。是不是 STL 常数太大了还是什么不可告人的原因导致 TLE?
#include<algorithm>//airport
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n,m1,m2;
struct airline
{
int s,e;
bool operator<(airline const& other){return s<other.s;}
}domes[100009],inter[100009];
int domv[100009],intv[100009];
int domnxt[100009],intnxt[100009];
int domsiz[100009],intsiz[100009];
int domqzh[100009],intqzh[100009];
queue<int>domh,inth;
int main()
{
//freopen(...)
ios::sync_with_stdio(0);
cin>>n>>m1>>m2;
for(int i=1;i<=m1;i++)cin>>domes[i].s>>domes[i].e;
sort(domes+1,domes+m1+1);
int siz1=0;
while(siz1<m1)
{
int last=-1,lastval=0,head=0;
for(int i=1;i<=m1;i++)if(domes[i].s>last && domv[i]==0)
{
if(last==-1)domh.push(i),head=i;
domv[i]=1;
domnxt[lastval]=i;
last=domes[i].e;
lastval=i;
domsiz[head]++;
siz1++;
}
}
for(int i=1;i<=m2;i++)cin>>inter[i].s>>inter[i].e;
sort(inter+1,inter+m2+1);
int siz2=0;
while(siz2<m2)
{
int last=-1,lastval=0,head=0;
for(int i=1;i<=m2;i++)if(inter[i].s>last &&intv[i]==0)
{
if(last==-1)inth.push(i),head=i;
intv[i]=1;
intnxt[lastval]=i;
last=inter[i].e;
lastval=i;
intsiz[head]++;
siz2++;
}
}
for(int i=1;i<=n;i++)
{
if(domh.empty())domqzh[i]=domqzh[i-1];
else domqzh[i]=domqzh[i-1]+domsiz[domh.front()],domh.pop();
if(inth.empty())intqzh[i]=intqzh[i-1];
else intqzh[i]=intqzh[i-1]+intsiz[inth.front()],inth.pop();
}
int ans=-1;
for(int i=1;i<=n;i++)ans=max(ans,domqzh[i]+intqzh[n-i]);
cout<<ans;
return 0;
}