QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #818893 | #5173. 染色 | NineSuns | 0 | 16ms | 3740kb | C++14 | 806b | 2024-12-18 10:39:16 | 2024-12-18 10:39:16 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5005;
int n, q, f[N][2], a[N];
signed main () {
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);
// int ans = r-l;
f[l][0] = 0; f[l][1] = a[l+1] == a[l] ? 0 : 1;
for (int i = l;i < r;i++) {
f[i+1][0] = min(f[i][0]+(a[i] != a[i+1]), f[i][1]);
f[i+1][1] = min(f[i][0]+(a[i] != a[i+2])+(a[i+1] != a[i+2]), f[i][1]+(a[i+1] != a[i+2])+(a[i+1] != a[i+2]));
}
cout << r-l+f[r][0] << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
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:
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 1ms
memory: 3728kb
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:
3
result:
wrong answer 1st words differ - expected: '113194', found: '3'
Subtask #3:
score: 0
Wrong Answer
Test #15:
score: 0
Wrong Answer
time: 16ms
memory: 3592kb
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:
1351 2755 1778 2666 4860 5103 3017 1355 899 5176 7980 4961 955 943 823 7427 7822 5441 3892 3300 4571 1608 2590 40 922 308 4447 3966 3891 5853 4710 1691 445 1445 3699 5366 577 122 2087 7772 9304 2092 3186 3759 2945 429 741 4093 183 3298 1473 1636 7274 3069 6081 8249 1575 3885 370 4570 3365 1780 836 2...
result:
wrong answer 1st words differ - expected: '1322', found: '1351'
Subtask #4:
score: 0
Wrong Answer
Test #23:
score: 0
Wrong Answer
time: 1ms
memory: 3740kb
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:
2142 7993 4552 8111 3696 3046 3995 1596 516 1812 1075 3733 6999 5737 1778 2958 1418 4805 1536 7217 598 7222 3748 916 2528 2310 2666 3638 350 3564 1590 682 567 320 3484 2516 8573 3154 210 4763 5385 4786 858 5223 4735 734 1547 2125 5558 566 4716 3008 138 1240 3234 1604 6523 378 2046 14 184 2843 5655 6...
result:
wrong answer 1st words differ - expected: '1263815', found: '2142'