QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#518102#1669. Hard OptimizationMo_Han136WA 0ms3996kbC++209.7kb2024-08-13 15:45:362024-08-13 15:45:37

Judging History

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

  • [2024-08-13 15:45:37]
  • 评测
  • 测评结果：WA
  • 用时：0ms
  • 内存：3996kb
查看
  • [2024-08-13 15:45:36]
  • 提交

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][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]][3]+a[x].r-a[g[x][1]].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;
    }


	// printf("%d :[%d %d] :%d %d\n",x,a[x].l,a[x].r,f[x][0],pre[x][0]);
	// printf("%d :[%d %d] :%d %d\n",x,a[x].l,a[x].r,f[x][1],pre[x][1]);
	// printf("%d :[%d %d] :%d %d\n",x,a[x].l,a[x].r,f[x][2],pre[x][2]);
	// printf("%d :[%d %d] :%d %d\n",x,a[x].l,a[x].r,f[x][3],pre[x][3]);
}

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);
        }
    }
    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;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

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: 3912kb

input:

1
23 81

output:

58
23 81

result:

ok ok, n = 1, ans = 58

Test #3:

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

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: 3776kb

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: 3900kb

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: 3844kb

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: 3796kb

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: 3840kb

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: 0
Accepted
time: 0ms
memory: 3904kb

input:

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

output:

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

result:

ok ok, n = 8, ans = 78

Test #10:

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

input:

9
31 62
97 98
53 59
17 79
3 87
40 60
72 77
22 29
7 11

output:

69
31 40
97 98
53 59
59 72
11 22
40 53
72 77
22 29
7 11

result:

ok ok, n = 9, ans = 69

Test #11:

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

input:

10
77 78
43 49
60 75
11 32
81 94
64 67
17 19
52 53
40 76
46 48

output:

57
77 78
43 46
67 75
19 32
81 94
64 67
17 19
52 53
53 64
46 48

result:

ok ok, n = 10, ans = 57

Test #12:

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

input:

19
8314 8691
4849 5182
9756 9945
2065 2266
978 1381
9074 9104
4416 8279
36 8854
4637 5261
9068 9265
8980 9338
9601 9624
651 4145
7653 8067
1778 1799
845 1421
1385 1410
6408 7531
6733 7290

output:

7704
8314 8691
4849 5182
9756 9945
2065 2266
978 1381
9074 9104
5182 6733
2266 4637
4637 4849
9104 9265
8980 9074
9601 9624
1410 1778
7653 8067
1778 1799
845 978
1385 1410
7290 7531
6733 7290

result:

ok ok, n = 19, ans = 7704

Test #13:

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

input:

47
2724 2847
2977 2978
8838 9272
3428 3734
9479 9540
6930 7085
8431 8471
4289 5762
5515 5529
7237 7277
2255 4083
6793 7733
6013 6189
8752 9398
2603 2910
8066 8711
5899 7916
6263 6662
113 4133
3450 3572
4622 4973
1908 2043
328 776
8243 8247
6934 6995
5921 6006
3355 3420
2567 3036
5147 5185
2047 2054
...

output:

6676
2724 2847
2977 2978
8838 9272
3572 3734
9479 9540
6930 6934
8431 8471
4289 4776
5515 5529
7237 7277
2978 3355
6995 7237
6013 6189
9272 9388
2603 2724
8471 8711
7433 7916
6263 6277
2054 2603
3450 3572
4959 4973
1908 2043
497 665
8243 8247
6934 6995
5921 6006
3355 3420
2847 2977
5147 5185
2047 20...

result:

ok ok, n = 47, ans = 6676

Test #14:

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

input:

48
4735 4834
5477 5835
3971 4180
907 1845
5552 5819
410 1872
9909 9983
1116 1449
6544 7083
1368 1433
5077 5143
122 8492
6059 6129
1481 1580
3423 3492
3918 4391
7724 7754
7174 7352
6735 6767
8592 9365
86 96
3356 3419
4441 4499
331 2433
926 1069
9453 9761
2004 2122
8523 9817
7902 8314
9834 9843
2860 3...

output:

7585
4735 4834
5477 5552
3971 4180
1069 1368
5552 5819
410 667
9909 9983
1433 1449
6767 7083
1368 1433
5077 5143
2095 2860
6059 6129
1481 1580
3423 3492
4180 4391
7724 7754
7174 7352
6735 6767
8592 8717
86 96
3356 3419
4441 4499
1580 2004
926 1069
9453 9459
2004 2088
9125 9453
8241 8314
9834 9843
28...

result:

ok ok, n = 48, ans = 7585

Test #15:

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

input:

61
4857 4890
2474 2581
7705 7729
2151 2212
3831 4045
675 680
6791 7772
132 1181
5859 6029
1861 1948
6183 6258
5673 5708
9728 9892
5025 5451
8361 8431
1200 2605
5033 5221
5016 5503
9102 9122
6453 6475
6286 6307
3645 3828
7285 7658
3198 3203
6692 8039
9948 9974
9136 9140
7866 7970
784 888
4761 4836
13...

output:

6957
4857 4890
2474 2581
7705 7729
2151 2212
3831 3943
675 680
7127 7285
888 1181
5859 6029
1861 1948
6183 6258
5673 5678
9728 9763
5025 5033
8361 8391
2254 2474
5033 5221
5016 5025
9102 9122
6453 6475
6286 6307
3795 3828
7285 7658
3198 3203
6692 6884
9948 9974
9136 9140
7866 7970
784 888
4761 4836
...

result:

ok ok, n = 61, ans = 6957

Test #16:

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

input:

69
2356 2546
7498 7527
2114 2172
2866 4692
6101 6104
2607 2662
619 949
5495 5513
8013 8166
2704 2765
306 567
1192 1292
5241 6149
7468 7556
9455 9480
1926 1965
427 542
3033 3087
2218 2234
9423 9485
6312 6584
65 2857
1165 1341
4247 4615
7068 7241
8853 8971
9049 9061
7621 7747
6920 6925
2975 3405
8874 ...

output:

8167
2356 2546
7498 7527
2114 2172
4487 4692
6101 6104
2607 2662
619 845
5495 5513
8013 8166
2704 2765
542 567
1192 1292
5694 6101
7527 7556
9455 9480
1926 1965
427 542
3033 3087
2218 2234
9480 9485
6312 6433
65 427
1165 1192
4247 4359
7068 7241
8929 8971
9049 9061
7621 7747
6920 6925
2975 3033
8874...

result:

ok ok, n = 69, ans = 8167

Test #17:

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

input:

226
907689292 910731765
637315418 640270766
649957861 656645930
330108609 332693231
327790388 341052210
452058987 452711364
164678004 227157125
701219833 702883478
35857149 36022443
652977298 655883456
200127263 204937919
873141333 894247545
964266670 986217229
168568045 174180280
743434879 76941787...

output:

830100588
907689292 910731765
637315418 640270766
650848689 654567327
330108609 332693231
332693231 335380835
452058987 452711364
174180280 200127263
701931176 702883478
35857149 36022443
654853981 655883456
200127263 204937919
879476755 884106954
980136568 981426908
168568045 174180280
757439693 76...

result:

wrong answer valid but inoptimal: expected 848026569, found 830100588
English 繁體中文 简体中文

服务器时间: 2024-11-29 18:39:36 | 开源项目