QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#740695	#5173. 染色	posvii	21	11ms	8580kb	C++14	744b	2024-11-13 11:09:29	2024-11-13 11:09:29

Judging History

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

[2024-11-13 11:09:29]
评测

测评结果：21
用时：11ms
内存：8580kb

查看

[2024-11-13 11:09:29]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e6+5;
int n,q,a[MAXN],las[MAXN],f[MAXN][25];
signed main() {
	#ifndef ONLINE_JUDGE
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	#endif
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;++i) {
		cin>>a[i];
		f[i][0]=max(las[a[i]],f[i-1][0]),las[a[i]]=i;
	}
	for(int j=1;j<=19;++j) {
		for(int i=n;f[i][j-1];--i) {
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
	while(q--) {
		int l,r;
		cin>>l>>r;
		if(l>r) swap(l,r);
		int ans=(r-l)*2;
		while(f[r][0]>=l) {
			r=f[r][0];
			--ans;
		}
		// for(int j=19;j>=0;--j) {
		// 	if(f[r][j]>=l) r=f[r][j]-1,ans-=1<<j;
		// }
		printf("%d\n",ans);
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 2ms

memory: 6772kb

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:

ok 100 tokens

Test #2:

score: 3

Accepted

time: 0ms

memory: 8580kb

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:

result:

ok 100 tokens

Test #3:

score: 3

Accepted

time: 2ms

memory: 6736kb

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:

result:

ok 100 tokens

Test #4:

score: 3

Accepted

time: 0ms

memory: 6832kb

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:

result:

ok 100 tokens

Test #5:

score: 3

Accepted

time: 2ms

memory: 6832kb

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:

result:

ok 100 tokens

Test #6:

score: 3

Accepted

time: 2ms

memory: 8232kb

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:

result:

ok 100 tokens

Subtask #2:

score: 0

Time Limit Exceeded

Test #7:

score: 0

Time Limit Exceeded

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

Accepted

Test #15:

score: 18

Accepted

time: 0ms

memory: 6284kb

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

Accepted

time: 3ms

memory: 8040kb

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

Accepted

time: 0ms

memory: 6336kb

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

Accepted

time: 10ms

memory: 6272kb

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

Accepted

time: 10ms

memory: 6260kb

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

Accepted

time: 11ms

memory: 8040kb

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

Accepted

time: 4ms

memory: 6468kb

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

Accepted

time: 4ms

memory: 6396kb

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

Time Limit Exceeded

Test #23:

score: 0

Time Limit Exceeded

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

output: