QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#517839#1669. Hard OptimizationEricQianWA 1ms3984kbC++209.4kb2024-08-13 14:06:342024-08-13 14:06:34

Judging History

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

  • [2024-08-13 14:06:34]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3984kb
查看
  • [2024-08-13 14:06:34]
  • 提交

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(!len)return;
    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(p && (a[i].r<a[p].l || a[i].l>a[p].r))p=fa[p];
        if(p){g[p].pb(i);fa[i]=p;}p=i;
    }
    rep(i,1,n)if(!fa[i]){
        dfs(i);
        ANS+=f[i][0];
        DFS(i,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: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3772kb

input:

4
1 10
2 3
5 9
6 7

output:

7
3 6
2 3
7 9
6 7

result:

ok ok, n = 4, ans = 7

Test #2:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

1
23 81

output:

58
23 81

result:

ok ok, n = 1, ans = 58

Test #3:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

2
8 30
56 93

output:

59
8 30
56 93

result:

ok ok, n = 2, ans = 59

Test #4:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

3
36 93
43 67
45 62

output:

50
62 93
43 45
45 62

result:

ok ok, n = 3, ans = 50

Test #5:

score: 0
Accepted
time: 0ms
memory: 3984kb

input:

4
72 85
17 70
54 65
22 33

output:

56
72 85
33 54
54 65
22 33

result:

ok ok, n = 4, ans = 56

Test #6:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

5
1 11
46 69
19 78
48 58
27 44

output:

59
1 11
46 48
58 78
48 58
27 44

result:

ok ok, n = 5, ans = 59

Test #7:

score: 0
Accepted
time: 0ms
memory: 3924kb

input:

6
8 53
64 67
28 33
60 62
13 19
86 97

output:

47
33 53
64 67
28 33
60 62
13 19
86 97

result:

ok ok, n = 6, ans = 47

Test #8:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

7
2 78
26 52
56 77
86 97
38 43
69 71
37 51

output:

76
2 37
43 52
56 69
86 97
38 43
69 71
37 38

result:

ok ok, n = 7, ans = 76

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3840kb

input:

8
17 71
1 97
25 27
76 93
40 52
23 53
55 68
82 83

output:

103
52 55
1 25
25 27
83 93
40 52
27 40
55 68
82 83

result:

wrong answer incorrect sum of length: declared 103, actual 78
English 繁體中文 简体中文

Server Time: 2024-11-29 16:30:37 | OpenSource Project