QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #742557 | #5173. 染色 | Erinyes | 3 | 833ms | 25264kb | C++14 | 860b | 2024-11-13 16:48:13 | 2024-11-13 16:48:13 |
Judging History
answer
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,q;
int a[N],f[10005][514];
signed main(){
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
#ifndef ONLINE_JUDGE
freopen(".in","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
while(q--){
int l,r;cin>>l>>r;if(l>r)swap(l,r);
for(int i=1;i<=100;i++)f[l][i]=(a[l]!=i);
for(int i=l+1;i<=r;i++){
for(int j=1;j<=100;j++){
f[i][j]=f[i-1][j]+1+(a[i]!=j);
// for(int k=1;k<=100;k++){
// f[i][j]=min(f[i][j],f[i-1][k]+1+(k!=j)+(a[i]!=j));
// }
}
for(int k=1;k<=100;k++){
f[i][a[i]]=min(f[i][a[i]],f[i-1][k]+1+(k!=a[i]));
}
}int ans=1e9;
for(int i=1;i<=100;i++)ans=min(ans,f[r][i]);
cout<<ans<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 32ms
memory: 25228kb
input:
10000 100 84 85 52 2 78 53 20 21 23 76 37 44 18 5 37 8 81 65 46 58 69 1 69 37 53 46 37 35 35 89 1 77 35 6 46 59 89 46 25 55 50 38 61 67 44 23 29 24 46 4 42 15 34 77 20 34 83 79 12 50 69 26 38 14 9 66 80 72 22 26 9 68 35 38 19 84 92 30 83 62 100 71 81 60 7 37 64 50 33 60 86 75 45 78 32 53 3 48 87 60 ...
output:
3668 4575 5976 8382 729 7013 183 7320 492 1140 253 2249 13226 6254 456 7507 2162 10481 1791 2675 4801 293 5997 627 6654 6179 11414 2712 3157 7836 17782 511 5486 17835 9564 6147 4996 14577 670 463 15613 12669 8872 7833 10987 6603 6399 5023 9102 8529 2173 10299 2694 12537 4958 2144 8809 1907 6476 2828...
result:
ok 100 tokens
Test #2:
score: 3
Accepted
time: 33ms
memory: 24928kb
input:
10000 100 84 17 43 100 30 77 73 68 15 91 62 47 89 90 53 43 67 81 64 54 88 88 22 31 76 38 17 87 93 31 67 43 50 27 40 70 43 55 73 82 8 15 64 3 28 27 30 56 1 82 40 51 21 71 74 45 20 99 66 40 99 27 47 65 82 31 43 50 18 48 23 67 56 57 34 39 84 55 66 22 12 83 87 56 15 1 92 26 71 60 76 41 27 32 47 47 5 83 ...
output:
2917 8523 9021 3406 7965 4359 3941 5506 1084 1614 481 81 4058 2180 5726 1694 731 3824 6639 3600 3929 622 10583 8213 7195 14275 5000 10076 11773 9826 11101 584 13966 3123 4956 16159 11421 1277 9028 15023 9857 7385 2167 12910 2557 2507 4890 4412 8218 2327 491 9487 814 3470 13399 4675 13129 17628 2654 ...
result:
ok 100 tokens
Test #3:
score: 3
Accepted
time: 29ms
memory: 24204kb
input:
10000 100 32 36 55 41 29 97 62 59 25 9 39 50 64 10 8 63 18 20 92 96 74 39 54 39 21 64 99 42 78 36 89 96 81 41 73 41 79 14 29 52 20 68 98 27 12 25 79 32 43 38 76 84 34 62 23 48 33 63 38 62 38 16 6 80 34 90 78 85 34 4 66 14 72 58 87 97 8 36 45 49 72 7 58 39 60 32 1 58 31 4 96 73 67 17 65 93 36 34 82 8...
output:
915 7882 4456 5090 11266 13587 10142 1715 9756 10320 10688 10946 1041 6819 7585 11004 2376 4515 9410 14700 11609 1002 3283 5657 11717 3351 5542 2648 8219 211 10706 6756 1920 15593 9567 1829 2192 15856 9371 5313 11960 1845 1151 14764 5195 700 7592 2487 13781 3557 5660 3063 1234 1026 10701 13399 8886 ...
result:
ok 100 tokens
Test #4:
score: 3
Accepted
time: 26ms
memory: 25104kb
input:
10000 100 1 11 1 48 3 13 2 49 2 98 3 41 3 29 3 1 3 28 3 64 1 86 2 62 3 47 1 51 1 4 3 11 2 17 3 41 1 5 2 71 1 63 2 38 1 41 3 86 1 38 2 25 1 56 2 64 1 58 2 3 2 96 1 57 1 37 3 98 2 84 2 30 3 20 1 42 2 29 1 26 3 63 2 43 2 67 3 76 1 86 3 82 2 57 1 11 3 72 1 97 1 50 3 78 3 96 3 3 2 89 1 52 2 4 1 79 2 8 1 ...
output:
3247 4211 7240 9159 5437 560 1806 7335 9493 178 2975 5263 4077 9925 2564 5853 6617 7426 472 4861 70 3717 2587 5337 11345 4078 4262 1374 8587 8758 247 8562 10193 967 6174 1331 14658 3522 4343 6363 15336 1626 7881 5480 5926 130 14564 3918 9515 1625 1700 2996 8011 10032 3195 13157 14630 5981 5568 5635 ...
result:
ok 100 tokens
Test #5:
score: 3
Accepted
time: 37ms
memory: 25264kb
input:
10000 100 1 75 2 61 1 93 1 74 2 100 1 3 3 46 2 35 3 67 1 78 1 23 2 75 2 76 2 86 3 95 1 23 1 97 1 82 1 32 2 37 1 1 1 11 1 70 1 95 3 88 3 94 3 97 3 39 3 8 2 90 2 13 3 41 3 33 3 50 3 13 3 87 3 18 2 47 2 41 2 44 1 94 1 87 3 60 2 86 1 70 2 75 2 44 2 17 2 95 2 90 2 76 3 3 1 28 3 66 2 65 1 48 1 2 1 63 1 10...
output:
10931 533 3443 1214 1825 4206 7142 1472 1562 6028 618 9559 501 2796 12337 3511 12351 5459 13074 8159 4684 2508 11605 8231 11646 5209 1175 6346 2665 4952 12436 4120 3712 3069 10795 3114 2912 12743 6998 1822 9440 7080 1930 431 294 6709 6148 7049 6792 1813 11850 13314 74 8352 5258 3855 2678 6790 9055 6...
result:
ok 100 tokens
Test #6:
score: 3
Accepted
time: 95ms
memory: 25264kb
input:
10000 100 4 73 53 79 63 67 22 41 3 90 3 11 86 58 81 98 66 31 92 51 25 27 90 95 57 65 1 73 21 11 4 44 5 26 2 2 72 1 46 80 24 20 42 58 48 34 84 66 35 86 56 30 2 68 68 74 59 9 32 3 68 1 98 75 17 6 55 24 67 34 56 23 55 75 56 69 26 11 35 55 54 87 96 56 4 39 61 4 92 7 24 96 88 7 95 15 88 52 59 62 72 9 20 ...
output:
18957 19017 18891 19110 18997 18929 18891 19005 19012 18956 18985 18915 19071 18829 18922 18972 19072 19037 18966 19018 18854 19006 19083 18868 19015 18961 18905 18797 19029 18906 19053 19041 18919 19100 18893 19008 18986 18920 18972 18961 18967 18970 19029 19041 18953 18919 19126 19109 19137 19022 ...
result:
ok 100 tokens
Subtask #2:
score: 0
Runtime Error
Test #7:
score: 0
Runtime Error
input:
100000 100000 3 2 3 3 3 3 2 3 2 1 3 1 1 1 3 2 1 3 1 2 2 1 3 1 2 2 1 1 1 3 2 1 3 3 3 3 1 1 1 2 3 3 2 1 1 1 3 1 3 1 3 2 1 3 2 3 3 2 3 3 2 3 3 3 3 3 2 3 2 3 1 3 3 3 3 3 3 3 1 2 3 3 1 3 1 1 2 2 3 1 1 2 3 2 3 1 3 2 1 3 2 3 2 1 1 3 3 1 3 1 2 2 2 3 2 3 2 3 2 1 1 3 1 3 2 2 3 3 3 1 2 2 3 3 2 1 3 1 2 2 2 3 2 ...
output:
result:
Subtask #3:
score: 0
Wrong Answer
Test #15:
score: 0
Wrong Answer
time: 833ms
memory: 17436kb
input:
5000 5000 256 63 197 36 75 66 33 72 27 75 66 248 29 166 209 252 141 95 84 226 147 249 116 94 192 256 199 273 182 166 116 274 27 211 154 144 283 23 53 110 215 11 164 284 161 221 251 96 43 47 18 115 12 51 156 61 116 209 93 98 47 165 174 106 83 67 184 75 12 290 183 197 112 240 67 56 215 148 104 5 141 2...
output:
1335 2729 1757 2632 4811 5046 2991 1342 890 5117 7889 4901 942 932 811 7345 7739 5387 3851 3268 4512 1586 2558 40 912 305 4403 3929 3841 5785 4667 1675 441 1432 3651 5303 570 119 2064 7689 9202 2073 3144 3711 2918 428 733 4056 180 3262 1449 1612 7193 3033 6012 8163 1562 3835 367 4512 3322 1761 823 2...
result:
wrong answer 1st words differ - expected: '1322', found: '1335'
Subtask #4:
score: 0
Runtime Error
Test #23:
score: 0
Runtime Error
input:
1000000 1000000 1105 3246 1880 3554 818 2331 2576 4140 149 4562 3498 3536 3400 4788 4363 4742 1216 4218 4032 1701 1489 4889 1761 3022 3145 4945 3067 4304 5016 4624 1612 13 1335 3613 1086 2210 386 3464 1156 3352 4341 5006 3465 3900 622 654 1826 2983 1250 4164 3335 4308 2995 1982 1347 4335 2535 5054 4...