QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#350419	#5173. 染色	ANIG	0	1ms	3768kb	C++14	1.1kb	2024-03-10 18:23:52	2024-03-10 18:23:52

Judging History

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

[2024-03-10 18:23:52]
评测

测评结果：0
用时：1ms
内存：3768kb

查看

[2024-03-10 18:23:52]
提交

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;
    for(int i=l+1;i<=r;i++){
        for(int j=i-1;j>lst[i];j--){
            f[i]=min(f[i],f[j]+i-j);
        }
        f[i]=min(f[i],f[lst[i]]+i-lst[i]-1);
    }
    return f[r];
}
int solve2(int l,int r){
    memset(f,0x3f,sizeof(f));
    f[r]=0;
    for(int i=r-1;i>=l;i--){
        for(int j=i+1;j<nxt[i];j++){
            f[i]=min(f[i],f[j]+j-i);
        }
        f[i]=min(f[i],f[nxt[i]]+nxt[i]-i-1);
    }
    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";
    }
}

源文件, 语言: C++14

详细

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 1ms

memory: 3768kb

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:

2
152
77
4557430888798830374
4557430888798830347

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

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: 0

Time Limit Exceeded

Test #15:

score: 0

Time Limit Exceeded

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:

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