QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#518102 | #1669. Hard Optimization | Mo_Han136 | WA | 0ms | 3996kb | C++20 | 9.7kb | 2024-08-13 15:45:36 | 2024-08-13 15:45:37 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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