这个代码的时间复杂度是?
查看原帖
这个代码的时间复杂度是?
561708
long_int楼主2022/3/21 10:36

过了所有官方数据:https://www.luogu.com.cn/record/71975415

不过CCF貌似96分

#include<bits/stdc++.h>
using namespace std;
int n,m1,m2,s,v;
int b,c[150000],d[150000];
int c2[150000],d2[150000];
int ans=-1;
struct node{
    int x,y;
    }a[150000];
int cmp(node p,node q){
    if(p.x!=q.x)
        return p.x<q.x;
    else
        return p.y<q.y;
    }
void work1(int aaa){
    for(int i=1;i<=s;i++)
        if(c[i]<a[aaa].x){
            c[i]=a[aaa].y;
            c2[i]++;
            return;}
    s++;
    c[s]=a[aaa].y;
    c2[s]=1;}
void work2(int bbb){
    for(int i=1;i<=v;i++)
        if(d[i]<a[bbb].x){
            d[i]=a[bbb].y;
            d2[i]++;
            return;}
    v++;
    d[v]=a[bbb].y;
    d2[v]=1;}
void work3(){
    for(int i=0;i<=n;i++)
        ans=max(ans,c2[i]+d2[n-i]);
    cout<<ans;}
int main()
{
 //   freopen("airport.in","r",stdin);
 //   freopen("airport.out","w",stdout);
    cin>>n>>m1>>m2;
    for(int i=1;i<=m1;i++)
        cin>>a[i].x>>a[i].y;
    s=1;
    sort(a+1,a+m1+1,cmp);
    c[1]=a[1].y;
    c2[1]=1;
    for(int i=2;i<=m1;i++)
        work1(i);
    for(int i=2;i<=n;i++)
        c2[i]=c2[i-1]+c2[i];
    for(int i=1;i<=m2;i++)
        cin>>a[i].x>>a[i].y;
    v=1;
    sort(a+1,a+m2+1,cmp);
    d[1]=a[1].y;
    d2[1]=1;
    for(int i=2;i<=m2;i++)
        work2(i);
    for(int i=2;i<=n;i++)
        d2[i]=d2[i-1]+d2[i];
    work3();
    return 0;}
2022/3/21 10:36
加载中...