15pts求助
查看原帖
15pts求助
529262
AkeRi楼主2023/3/25 09:01
/*

by L1rs1ngzN1sLyr

*/
#include<bits/stdc++.h>
const int AI=1e3+9;
const int KI=1e6+2;
const int CI=1e7+3;
const int iINF=INT_MAX;
int read(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}

int tr[KI],bj,n=read(),ans1[KI],ans2[KI],ans=-iINF;
struct plane{int t,l;}a[KI],b[KI];
void update(int u){tr[u]=std::min(tr[u<<1],tr[u<<1|1]);}
void build(int u,int l,int r)
{ 
    tr[u]=iINF;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    update(u);
} 
void change(int u,int l,int r,int p,int k)
{
    if(l==r)
    {
        tr[p]=k;
        if(bj==1) ans1[p]++;
        else ans2[p]++;
        return ;
    }
    int mid=(l+r)>>1;
    if(p<=mid) change(u<<1,l,mid,p,k);
    if(p>mid) change(u<<1|1,mid+1,r,p,k);
    update(u);
}
void find(int u,int l,int r,int a,int b)
{
    if(l==r)
    {
        tr[l]=b;
        if(bj==1) ans1[l]++;
        else ans2[l]++;
        return ;
    }
    int mid=(l+r)>>1;
    if(tr[u<<1]<a) find(u<<1,l,mid,a,b); 
    else find(u<<1|1,mid+1,r,a,b);
    update(u);
}
bool mys(plane a,plane b){return a.t<b.t;}
int main()
{
    int m1=read(),m2=read();
    for(int i=1;i<=m1;i++) a[i].t=read(),a[i].l=read();
    for(int i=1;i<=m2;i++) b[i].t=read(),b[i].l=read();
    int cnt=0;
    std::sort(a+1,a+m1+1,mys);
    std::sort(b+1,b+m2+1,mys);
    build(1,1,m1);
    for(int i=1;i<=m1;i++)
    {
        if(tr[1]>a[i].t)
        {
            cnt++;
            change(1,1,m1,cnt,a[i].l);
            continue;
        }
        find(1,1,m1,a[i].t,a[i].l);
    }
    bj=2,cnt=0;
    build(1,1,m2);
    for(int i=1;i<=m2;i++)
    {
        if(tr[1]>b[i].t)
        {
            cnt++;
            change(1,1,m2,cnt,b[i].l);
            continue;
        }
        find(1,1,m2,b[i].t,b[i].l);
    }
    for(int i=1;i<=n;i++) ans1[i]+=ans1[i-1],ans2[i]+=ans2[i-1];
    for(int i=0;i<=n;i++) ans=std::max(ans,ans1[i]+ans2[n-i]);
    std::cout<<ans<<'\n';
}
2023/3/25 09:01
加载中...