QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#350425	#5173. 染色	ANIG	18	17ms	3912kb	C++14	1.1kb	2024-03-10 18:27:24	2024-03-10 18:27:24

Judging History

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

[2024-03-10 18:27:24]
评测

测评结果：18
用时：17ms
内存：3912kb

查看

[2024-03-10 18:27:24]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5000+5;
int n,m,w[N],f[N],lst[N],nxt[N],wz[N];
int solve1(int l,int r){
    memset(f,0x3f,sizeof(f));
    f[l]=0;int mn=-l;
    for(int i=l+1;i<=r;i++){
        f[i]=mn+i;
        f[i]=min(f[i],f[lst[i]]+i-lst[i]-1);
        mn=min(mn,f[i]-i);
        assert(mn==f[i]-i);
    }
    return f[r];
}
int solve2(int l,int r){
    memset(f,0x3f,sizeof(f));
    f[r]=0;int mn=r;
    for(int i=r-1;i>=l;i--){
        f[i]=mn-i;
        f[i]=min(f[i],f[nxt[i]]+nxt[i]-i-1);
        mn=min(mn,f[i]+i);
    }
    return f[l];
}
int solve(int l,int r){
    if(l<=r)return solve1(l,r)+r-l;
    return solve2(r,l)+l-r;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        lst[i]=wz[w[i]];
        wz[w[i]]=i;
    }
    for(int i=1;i<=n;i++)wz[i]=n+1;
    for(int i=n;i>=1;i--){
        nxt[i]=wz[w[i]];
        wz[w[i]]=i;
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<solve(l,r)<<"\n";
    }
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 1ms

memory: 3792kb

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:

result:

wrong answer 1st words differ - expected: '3668', found: '2'

Subtask #2:

score: 0

Wrong Answer

Test #7:

score: 0

Wrong Answer

time: 1ms

memory: 3724kb

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:

0
2

result:

wrong answer 1st words differ - expected: '113194', found: '0'

Subtask #3:

score: 18

Accepted

Test #15:

score: 18

Accepted

time: 16ms

memory: 3860kb

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:

result:

ok 5000 tokens

Test #16:

score: 0

Accepted

time: 15ms

memory: 3764kb

input:

5000 5000
180 296 137 108 236 226 19 135 16 42 151 140 223 244 115 170 230 207 143 65 195 219 77 119 170 197 223 65 64 217 206 157 100 52 202 192 19 193 281 229 212 183 63 220 261 66 209 32 63 190 144 221 180 248 29 265 152 141 212 50 129 237 281 270 261 192 104 55 133 12 92 91 61 258 51 172 244 257...

output:

result:

ok 5000 tokens

Test #17:

score: 0

Accepted

time: 15ms

memory: 3868kb

input:

5000 5000
152 143 107 44 171 299 88 120 221 238 145 137 152 30 196 218 31 216 16 39 206 111 212 195 91 45 107 165 132 260 264 57 217 9 223 194 137 59 132 194 286 248 28 95 219 236 144 145 76 69 53 127 91 226 15 277 60 180 114 122 112 96 108 283 55 50 204 123 69 29 136 134 42 283 240 164 33 17 143 10...

output:

result:

ok 5000 tokens

Test #18:

score: 0

Accepted

time: 17ms

memory: 3912kb

input:

5000 5000
7 4 1209 6 3 2 332 4 6 2 657 7 8 5 368 6 3 1 2973 4 1 2 1643 3 8 4 1694 4 7 2 1933 5 5 3 1973 5 3 6 1401 2 8 3 1040 6 4 3 2227 5 4 1 2731 3 4 5 352 5 4 5 2322 8 8 4 232 5 8 1 453 3 4 5 326 5 7 4 697 5 3 2 2147 6 8 8 1152 5 7 7 2473 2 8 1 2891 6 1 1 2272 5 1 6 2213 3 1 3 801 5 5 5 576 7 3 1...

output:

result:

ok 5000 tokens

Test #19:

score: 0

Accepted

time: 16ms

memory: 3776kb

input:

5000 5000
4 3 103 4 8 7 161 4 7 7 140 5 1 6 67 8 6 4 205 1 6 2 21 4 2 2 282 2 4 1 250 5 5 2 245 6 7 6 244 5 4 4 260 7 5 5 179 5 5 5 154 5 2 3 94 4 6 8 135 1 1 2 75 2 3 5 249 4 3 3 56 1 4 8 270 2 8 6 73 2 6 6 266 1 1 6 278 8 8 2 289 8 7 4 183 2 1 2 31 3 1 2 272 7 5 8 76 5 6 2 184 8 5 7 148 5 3 6 168 ...

output:

result:

ok 5000 tokens

Test #20:

score: 0

Accepted

time: 17ms

memory: 3772kb

input:

5000 5000
6 2 14 6 7 2 17 6 8 4 13 6 6 2 22 1 4 2 3 3 5 1 27 3 4 8 3 6 1 3 23 5 2 8 2 3 4 3 26 4 1 2 18 3 6 2 9 6 1 2 24 8 7 1 26 8 3 1 29 1 6 6 12 5 6 4 11 1 3 3 11 5 5 7 22 5 4 8 30 6 7 3 11 1 4 3 19 3 2 3 21 2 1 2 14 4 3 1 24 6 5 3 30 3 8 8 18 6 1 6 24 3 4 2 3 7 2 6 28 2 7 2 7 1 5 6 16 4 6 7 26 8...

output:

result:

ok 5000 tokens

Test #21:

score: 0

Accepted

time: 16ms

memory: 3764kb

input:

5000 5000
7 65 24 32 64 13 57 54 44 52 28 17 54 54 9 1 33 50 52 18 52 54 45 65 52 39 10 16 16 27 58 65 18 16 7 1 58 2 32 52 15 64 50 1 56 26 21 45 26 22 35 9 46 46 22 35 20 55 22 22 13 35 15 36 50 14 33 35 15 24 34 29 12 53 50 12 12 22 64 63 64 6 56 53 54 63 41 30 18 42 31 32 25 37 7 38 13 65 53 65 ...

output:

result:

ok 5000 tokens

Test #22:

score: 0

Accepted

time: 16ms

memory: 3860kb

input:

5000 5000
66 49 61 50 10 54 16 40 35 51 36 53 28 42 12 9 1 21 64 39 61 2 14 6 26 59 40 47 45 55 40 9 51 44 59 32 64 12 65 51 51 13 58 45 50 30 59 28 22 50 44 3 31 61 30 59 20 17 4 29 26 21 1 32 61 51 63 4 12 35 63 10 21 10 60 29 21 55 40 44 13 25 46 9 23 12 40 21 56 41 11 20 16 47 23 39 49 13 46 56 ...

output:

result:

ok 5000 tokens

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...