QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #359666 | #5173. 染色 | zyc070419 | 0 | 15ms | 11912kb | C++14 | 790b | 2024-03-20 19:50:36 | 2024-03-20 19:50:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
inline int read() {
char ch = getchar(); int x = 0;
while (!isdigit(ch)) {ch = getchar();}
while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
return x;
}
int n, T, a[N], lst[N], pre[N], val[N];
int main() {
n = read(); T = read();
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i <= n; ++i) lst[i] = 0;
for (int i = 1; i <= n; ++i) {
pre[i] = lst[a[i]];
lst[a[i]] = i;
for (int j = pre[i] + 1; j < i; ++j) val[i] = max(val[i], pre[j]);
}
while (T--) {
int l = read(), r = read(), ans;
if (l > r) l ^= r ^= l ^= r;
ans = 2 * (r - l);
for (int i = l; i <= r; ++i)
if (pre[i] >= l && val[i] < l) ans--;
printf("%d\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 10008kb
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:
3808 4756 6209 8702 753 7285 188 7598 511 1185 261 2330 13729 6497 472 7798 2234 10892 1856 2769 4985 300 6226 648 6919 6419 11844 2815 3282 8135 18461 530 5692 18516 9937 6388 5188 15139 690 478 16212 13155 9215 8132 11402 6862 6648 5222 9453 8855 2260 10698 2787 13026 5142 2227 9139 1979 6719 2942...
result:
wrong answer 1st words differ - expected: '3668', found: '3808'
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:
128352 150898 62213 7320 10432 88757 106496 33161 44093 126519 75567 8158 74875 48480 50589 55888 12573 122113 81269 12098 5356 98810 53110 85915 30888 12410 13902 67421 21123 62474 13153 8881 6255 43915 76308 66137 19211 79437 79787 60825 58788 630 20952 135949 4551 49083 70881 38497 11190 28347 37...
result:
Subtask #3:
score: 0
Wrong Answer
Test #15:
score: 0
Wrong Answer
time: 15ms
memory: 11912kb
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:
1352 2753 1778 2664 4866 5103 3022 1355 898 5179 7987 4965 954 940 822 7433 7831 5449 3896 3300 4571 1606 2591 40 922 305 4453 3970 3889 5860 4717 1691 443 1447 3697 5368 575 121 2087 7780 9315 2092 3184 3757 2947 427 738 4098 182 3302 1472 1634 7281 3071 6084 8260 1573 3883 369 4569 3366 1781 831 2...
result:
wrong answer 1st words differ - expected: '1322', found: '1352'
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...