QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#517814	#1669. Hard Optimization	EricQian	Compile Error	/	/	Python3	9.3kb	2024-08-13 14:00:50	2024-08-13 14:00:50

Judging History

你现在查看的是最新测评结果

[2024-08-13 14:00:50]
评测

测评结果：Compile Error
用时：0ms
内存：0kb

查看

[2024-08-13 14:00:50]
提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define erep(i,a) for(int i=head[a];i;i=e[i].nxt)

using namespace std;
const int M=2005;
int n;
struct node{
    int l,r,id;
    bool operator < (const node &_)const{
        return l<_.l;
    }
}a[M],ans[M];
int ANS;
int f[M][4],pre[M][4],fa[M],fp[M];
vector<int> g[M];

int sum[M];
void dfs(int x){
    if(!g[x].size()){
        f[x][0]=f[x][1]=f[x][2]=f[x][3]=a[x].r-a[x].l;
        pre[x][0]=pre[x][1]=pre[x][2]=pre[x][3]=0;
        return;
    }
    rep(i,0,g[x].size()-1){
        int y=g[x][i];
        dfs(y);
    }
    rep(i,0,g[x].size()-1){
        int y=g[x][i];
        sum[i+1]=sum[i]+f[y][0];
    }
    int len=g[x].size();
    int L=0;
//j=0
    L=a[g[x][0]].l-a[x].l+f[g[x][0]][1]+sum[len]-sum[1];
    if(L>f[x][0])f[x][0]=L,pre[x][0]=0;
    rep(i,1,len-1){
        int y=g[x][i-1];
        int z=g[x][i];
        L=sum[i-1]+f[y][2]+a[z].l-a[y].r+f[z][1]+sum[len]-sum[i+1];
        if(L>f[x][0])f[x][0]=L,pre[x][0]=i;
    }
    L=sum[len-1]+f[g[x][len-1]][2]+a[x].r-a[g[x][len-1]].r;
    if(L>f[x][0])f[x][0]=L,pre[x][0]=len;

//j=1
    if(len==1){
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][1];
        if(L>f[x][1])f[x][1]=L,pre[x][1]=0;
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][3]+a[x].r-a[g[x][0]].r;
        if(L>f[x][1])f[x][1]=L,pre[x][1]=1;
    }
    if(len>=2){
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][1]+sum[len]-sum[1];
        if(L>f[x][1])f[x][1]=L,pre[x][1]=0;
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][3]+a[g[x][1]].l-a[g[x][0]].r+f[g[x][1]][1]+sum[len]-sum[2];
        if(L>f[x][1])f[x][1]=L,pre[x][1]=1;
        rep(i,2,len-1){
            int y=g[x][i-1];
            int z=g[x][i];
            L=a[g[x][0]].l-a[x].l+f[g[x][0]][1]+sum[i-1]-sum[1]+f[y][2]+a[z].l-a[y].r+f[z][1]+sum[len]-sum[i+1];
            if(L>f[x][1])f[x][1]=L,pre[x][1]=i;
        }
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][1]+sum[len-1]-sum[1]+f[g[x][len-1]][2]+a[x].r-a[g[x][len-1]].r;
        if(L>f[x][1])f[x][1]=L,pre[x][1]=len;
    }
    
//j=2
    if(len==1){
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][3]+a[x].r-a[g[x][0]].r;
        if(L>f[x][2])f[x][2]=L,pre[x][2]=0;
        L=f[g[x][0]][2]+a[x].r-a[g[x][0]].r;
        if(L>f[x][2])f[x][2]=L,pre[x][2]=1;
    }
    if(len>=2){
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][1]+sum[len-1]-sum[1]+f[g[x][len-1]][2]+a[x].r-a[g[x][len-1]].r;
        if(L>f[x][2])f[x][2]=L,pre[x][2]=0;
        rep(i,1,len-2){
            int y=g[x][i-1];
            int z=g[x][i];
            L=sum[i-1]-sum[0]+f[y][2]+a[z].l-a[y].r+f[z][1]+sum[len-1]-sum[i+1]+f[g[x][len-1]][2]+a[x].r-a[g[x][len-1]].r;
            if(L>f[x][2])f[x][2]=L,pre[x][2]=i;
        }
        L=sum[len-2]-sum[0]+f[g[x][len-2]][2]+a[g[x][len-1]].l-a[g[x][len-2]].r+f[g[x][len-1]][3]+a[x].r-a[g[x][len-1]].r;
        if(L>f[x][2])f[x][2]=L,pre[x][2]=len-1;
        L=sum[len-1]-sum[0]+f[g[x][len-1]][2]+a[x].r-a[g[x][len-1]].r;
        if(L>f[x][2])f[x][2]=L,pre[x][2]=len;
    }

//j=3
    if(len==1){
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][3]+a[x].r-a[g[x][0]].r;
        if(L>f[x][3])f[x][3]=L,pre[x][3]=0;
    }
    if(len==2){
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][1]+f[g[x][1]][2]+a[x].r-a[g[x][0]].r;
        if(L>f[x][3])f[x][3]=L,pre[x][3]=0;
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][3]+a[g[x][1]].l-a[g[x][0]].r+f[g[x][1]][3]+a[x].r-a[g[x][0]].r;
        if(L>f[x][3])f[x][3]=L,pre[x][3]=1;
    }
    if(len>=3){
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][1]+sum[len-1]-sum[1]+f[g[x][len-1]][2]+a[x].r-a[g[x][len-1]].r;
        if(L>f[x][3])f[x][3]=L,pre[x][3]=0;
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][3]+a[g[x][1]].l-a[g[x][0]].r+f[g[x][1]][1]+sum[len-1]-sum[2]+f[g[x][len-1]][2]+a[x].r-a[g[x][len-1]].r;
        if(L>f[x][3])f[x][3]=L,pre[x][3]=1;
        rep(i,2,len-2){
            int y=g[x][i-1];
            int z=g[x][i];
            L=a[g[x][0]].l-a[x].l+f[g[x][0]][1]+sum[i-1]-sum[1]+f[y][2]+a[z].l-a[y].r+f[z][1]+sum[len-1]-sum[i+1]+f[g[x][len-1]][2]+a[x].r-a[g[x][len-1]].r;
            if(L>f[x][3])f[x][3]=L,pre[x][3]=i;
        }
        L=a[g[x][0]].l-a[x].l+f[g[x][0]][1]+sum[len-2]-sum[1]+f[g[x][len-2]][2]+a[g[x][len-1]].l-a[g[x][len-2]].r+f[g[x][len-1]][3]+a[x].r-a[g[x][len-1]].r;
        if(L>f[x][3])f[x][3]=L,pre[x][3]=len-1;
    }


}

int L(int x,int p){
    if(pre[x][p]==0)return a[x].l;
    if(pre[x][p]==1)return L(g[x][0],3);
    return L(g[x][0],1);
}
int R(int x,int p){
    int len=g[x].size();
    if(pre[x][p]==len)return a[x].r;
    if(pre[x][p]==len-1)return R(g[x][len-1],3);
    return R(g[x][len-1],2);
}
void DFS(int x,int p){
    ans[x].l=a[x].l;
    ans[x].r=a[x].r;
    int len=g[x].size();
    int t=pre[x][p];
    if(t<=len-1){
        if(p==0)ans[x].r=L(g[x][t],1);
        if(p==1)ans[x].r=L(g[x][t],1);
        if(p==2){
            if(t==len-1)ans[x].r=L(g[x][t],3);
            else ans[x].r=L(g[x][t],1);
        }
        if(p==3){
            if(t==len-1)ans[x].r=L(g[x][t],3);
            else ans[x].r=L(g[x][t],1);ans[x].r=L(g[x][t],1);
        }
    }
    if(t>=1){
        if(p==0)ans[x].l=R(g[x][t-1],2);
        if(p==2)ans[x].l=R(g[x][t-1],2);
        if(p==1){
            if(t==1)ans[x].l=R(g[x][t-1],3);
            else ans[x].l=R(g[x][t-1],2);
        }
        if(p==3){
            if(t==1)ans[x].l=R(g[x][t-1],3);
            else ans[x].l=R(g[x][t-1],2);
        }
    }
    if(p==0){
        if(len==1){
            if(t==0)DFS(g[x][1-1],1);
            if(t==len)DFS(g[x][1-1],2);
        }
        if(len>=2){
            if(t==0){
                DFS(g[x][1-1],1);
                rep(i,2,len)DFS(g[x][i-1],0);
            }
            if(1<=t && t<=len-1){
                rep(i,1,t-1)DFS(g[x][i-1],0);
                DFS(g[x][t-1],2);
                DFS(g[x][t+1-1],1);
                rep(i,t+2,len)DFS(g[x][i-1],0);
            }
            if(t==len){
                rep(i,1,t-1)DFS(g[x][i-1],0);
                DFS(g[x][t-1],2);
            }
        }
    }
    if(p==1){
        if(len==1){
            if(t==0)DFS(g[x][1-1],1);
            if(t==1)DFS(g[x][1-1],3);
        }
        if(len>=2){
            if(t==0){
                DFS(g[x][1-1],1);
                rep(i,2,len)DFS(g[x][i-1],0);
            }
            if(t==1){
                DFS(g[x][1-1],3);
                DFS(g[x][2-1],1);
                rep(i,3,len)DFS(g[x][i-1],0);
            }
            if(2<=t && t<=len-1){
                DFS(g[x][1-1],1);
                rep(i,2,t-1)DFS(g[x][i-1],0);
                DFS(g[x][t-1],2);
                DFS(g[x][t+1-1],1);
                rep(i,t+2,len)DFS(g[x][i-1],0);
            }
            if(t==len){
                DFS(g[x][1-1],1);
                rep(i,2,len-1)DFS(g[x][i-1],0);
                DFS(g[x][len-1],2);
            }
        
        }
    }
    if(p==2){
        if(len==1){
            if(t==0)DFS(g[x][1-1],3);
            if(t==1)DFS(g[x][1-1],1);
        }
        if(len>=2){
            if(t==0){
                DFS(g[x][1-1],1);
                rep(i,2,len-1)DFS(g[x][i-1],0);
                DFS(g[x][len-1],2);
            }
            if(1<=t && t<=len-2){
                rep(i,1,t-1)DFS(g[x][i-1],0);
                DFS(g[x][t-1],2);
                DFS(g[x][t+1-1],1);
                rep(i,t+2,len-1)DFS(g[x][i-1],0);
                DFS(g[x][len-1],2);
            }
            if(t==len-1){
                rep(i,1,len-2)DFS(g[x][i-1],0);
                DFS(g[x][len-1-1],2);
                DFS(g[x][len-1],3);
            }
            if(t==len){
                rep(i,1,len-1)DFS(g[x][i-1],0);
                DFS(g[x][len-1],2);
            }
        }
    }
    if(p==3){
        if(len==1){
            DFS(g[x][1-1],3);
        }
        if(len==2){
            if(t==0)DFS(g[x][1-1],1),DFS(g[x][2-1],2);
            if(t==1)DFS(g[x][1-1],3),DFS(g[x][2-1],3);
        }
        if(len>=3){
            if(t==0){
                DFS(g[x][1-1],1);
                rep(i,2,len-1)DFS(g[x][i-1],0);
                DFS(g[x][len-1],2);
            }
            if(t==1){
                DFS(g[x][1-1],3);
                DFS(g[x][2-1],1);
                rep(i,3,len-1)DFS(g[x][i-1],0);
                DFS(g[x][len-1],2);
            }
            if(2<=t && t<=len-2){
                DFS(g[x][1-1],1);
                rep(i,2,t-1)DFS(g[x][i-1],0);
                DFS(g[x][t-1],2);
                DFS(g[x][t+1-1],1);
                rep(i,t+2,len-1)DFS(g[x][i-1],0);
                DFS(g[x][len-1],2);
            }
            if(t==len-1){
                DFS(g[x][1-1],1);
                rep(i,2,len-2)DFS(g[x][i-1],0);
                DFS(g[x][len-1-1],2);
                DFS(g[x][len-1],3);
            }
        }

    }
}
int main(){
    scanf("%d",&n);
    rep(i,1,n)scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;
    sort(a+1,a+n+1);
    rep(i,1,n)fp[a[i].id]=i;
    int p=1;
    rep(i,2,n){
        while(a[i].r<a[p].l || a[i].l>a[p].r)p=fa[p];
        g[p].pb(i);fa[i]=p;p=i;
    }
    dfs(1);
    ANS=f[1][0];
    DFS(1,0);
    printf("%d\n",ANS);
    rep(i,1,n)printf("%d %d\n",ans[fp[i]].l,ans[fp[i]].r);
    return 0;
}

Source code, Language: Python3

Details

  File "answer.code", line 9
    using namespace std;
          ^^^^^^^^^
SyntaxError: invalid syntax