QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #111789 | #6528. Sequence | Ignotus | 40 | 766ms | 58044kb | C++17 | 1.9kb | 2023-06-08 20:06:19 | 2023-06-08 20:06:21 |
Judging History
answer
#include <bits/stdc++.h>
#include "sequence.h"
const int N = 5e5 + 10;
int n, a[N];
int pmx[N], pmn[N], smx[N], smn[N];
std::vector <int> pos[N];
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
int mx[N << 2], mn[N << 2], tag[N << 2];
void pushup(int p){mx[p] = std::max(mx[ls], mx[rs]), mn[p] = std::min(mn[ls], mn[rs]);}
void push(int p, int k){mx[p] += k, mn[p] += k, tag[p] += k;}
void pushdown(int p){if(tag[p]) push(ls, tag[p]), push(rs, tag[p]), tag[p] = 0;}
void upd(int p, int l, int r, int ql, int qr, int k){
if(ql <= l && r <= qr) return push(p, k), void();
pushdown(p);
if(ql <= mid) upd(ls, l, mid, ql, qr, k);
if(qr > mid) upd(rs, mid + 1, r, ql, qr, k);
pushup(p);
}
int qry_mx(int p, int l, int r, int ql, int qr){
if(ql <= l && r <= qr) return mx[p];
int ret = -1e9; pushdown(p);
if(ql <= mid) ret = std::max(ret, qry_mx(ls, l, mid, ql, qr));
if(qr > mid) ret = std::max(ret, qry_mx(rs, mid + 1, r, ql, qr));
return ret;
}
int qry_mn(int p, int l, int r, int ql, int qr){
if(ql <= l && r <= qr) return mn[p];
int ret = 1e9; pushdown(p);
if(ql <= mid) ret = std::min(ret, qry_mn(ls, l, mid, ql, qr));
if(qr > mid) ret = std::min(ret, qry_mn(rs, mid + 1, r, ql, qr));
return ret;
}
#undef ls
#undef rs
#undef mid
int sequence(int _N, std::vector <int> _A){
n = _N;
for(int i = 1; i <= n; ++i) a[i] = _A[i - 1], pos[a[i]].push_back(i), upd(1, 0, n, i, n, 1);
int ans = 1;
for(int i = 1; i <= n; ++i) if(pos[i].size()){
for(auto p : pos[i]) pmn[p] = qry_mn(1, 0, n, 0, p - 1), smx[p] = qry_mx(1, 0, n, p, n);
for(auto p : pos[i]) upd(1, 0, n, p, n, -2);
for(auto p : pos[i]) pmx[p] = qry_mx(1, 0, n, 0, p - 1), smn[p] = qry_mn(1, 0, n, p, n);
int siz = pos[i].size();
for(int l = 0, r = 0; r < siz; ++r){
while(l <= r && (smx[pos[i][r]] - pmn[pos[i][l]]) * (smn[pos[i][r]] - pmx[pos[i][l]]) > 0) ++l;
ans = std::max(ans, r - l + 1);
}
}
return ans;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 3ms
memory: 26160kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 98 92 89 9 86 80 6 42 20 84 82 46 56 52 30 44 39 35 82 57 33 18 38 32 63 27 55 33 44 41 39 62 26 46 59 21 85 36 60 7 36 50 22 87 83 71 27 4 3 87 47 17 62 70 24 9 20 81 21 57 50 13 32 68 70 11 95 5 56 64 90 47 42 44 72 71 46 84 72 56 63 37 35 80 78 4 54 74 79 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 3
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 28260kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 96 1 6 1 4 6 2 5 1 1 2 8 2 4 4 1 9 8 9 8 5 3 6 6 4 9 4 2 8 8 8 2 9 1 3 6 6 1 6 5 5 3 7 9 7 1 8 5 6 8 5 1 1 4 9 6 7 2 6 6 7 4 2 2 8 5 6 4 8 2 6 5 8 6 1 6 2 1 3 4 6 3 6 8 2 5 7 8 2 4 1 5 6 2 3 6 6
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 18
result:
ok
Test #3:
score: 0
Accepted
time: 5ms
memory: 28140kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 99 1 3 5 1 2 4 1 3 4 1 5 5 3 1 1 4 2 1 4 5 5 4 1 4 4 2 1 2 2 1 5 2 4 2 1 5 1 3 3 4 3 2 3 1 3 2 2 4 1 5 4 2 2 2 4 5 3 4 3 2 3 4 5 4 5 1 2 2 2 5 3 1 3 5 1 2 1 2 1 2 3 1 4 4 4 5 3 3 3 5 1 3 4 2 4 4 2 1 2
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 19
result:
ok
Test #4:
score: 0
Accepted
time: 4ms
memory: 28188kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 100 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 100
result:
ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 26212kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 97 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 8...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 1
result:
ok
Test #6:
score: 0
Accepted
time: 4ms
memory: 26196kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 100 48 40 13 1 8 31 46 19 42 9 13 8 33 43 85 9 36 21 83 49 4 49 49 24 49 82 9 88 24 33 23 99 79 46 83 49 2 4 40 92 49 44 92 99 49 49 38 49 12 29 49 89 100 81 79 85 22 38 49 8 27 29 3 100 100 42 82 49 31 26 40 49 46 10 49 49 84 77 93 20 33 90 49 18 49 49 18 84...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 18
result:
ok
Test #7:
score: 0
Accepted
time: 1ms
memory: 28168kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 97 42 47 7 23 9 10 53 75 53 53 2 1 75 14 4 16 53 35 32 37 97 31 47 91 77 84 53 87 93 85 70 80 2 19 53 53 67 85 25 3 37 41 52 21 30 84 25 15 37 30 97 53 22 97 33 97 53 9 69 38 71 6 74 4 13 26 27 90 91 47 11 90 7 76 97 17 80 53 23 95 73 53 1 21 43 42 2 33 29 32...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 11
result:
ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 28196kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 98 72 73 8 81 47 26 17 61 93 69 95 7 25 42 15 45 17 88 42 94 68 49 23 50 93 42 97 43 11 7 83 42 43 42 57 12 76 54 61 76 71 42 62 87 87 7 42 83 92 47 72 66 88 1 23 51 42 26 74 42 84 70 59 42 83 14 60 81 53 56 42 20 56 8 92 69 42 76 42 24 87 70 4 80 79 61 66 93...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 5
result:
ok
Test #9:
score: 0
Accepted
time: 2ms
memory: 28160kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 99 85 88 94 94 59 47 63 75 75 40 38 35 59 56 81 48 96 47 46 34 96 62 35 46 83 34 95 34 69 48 15 10 3 92 67 34 38 92 84 84 42 49 86 63 82 65 39 89 80 14 34 69 55 42 67 34 68 86 15 72 18 96 2 7 1 89 16 68 65 97 52 38 92 34 87 16 2 62 34 18 34 74 34 8 21 77 45 8...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 7
result:
ok
Subtask #2:
score: 17
Accepted
Dependency #1:
100%
Accepted
Test #10:
score: 17
Accepted
time: 1ms
memory: 26232kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 1999 486 1494 1286 1247 138 393 816 1646 971 1657 1284 1320 702 194 602 1775 13 1856 61 1264 1005 681 1679 1174 718 1781 1407 97 365 1949 1805 1609 1066 637 98 1686 1361 584 146 1879 941 62 1433 1850 729 1754 71 1292 1945 1328 1705 362 591 407 998 1909 1690 2...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 4
result:
ok
Test #11:
score: 0
Accepted
time: 3ms
memory: 26216kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 1996 1475 182 1399 123 1593 884 1167 1543 663 302 16 217 1284 1777 1875 1996 1238 1368 52 1935 881 235 1437 1002 1000 1473 1248 540 139 282 850 451 797 1595 803 1050 293 1827 1677 1323 1617 1760 13 151 1329 74 1828 1609 532 1224 103 685 1040 48 88 238 501 873...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 3
result:
ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 26264kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 1996 12 36 13 34 17 23 24 32 24 36 28 31 27 19 26 31 24 6 42 32 19 43 25 32 13 39 34 39 24 29 15 32 16 28 36 2 3 37 7 42 34 11 43 25 31 17 43 24 27 43 6 28 17 25 33 44 41 14 27 11 2 5 20 20 7 17 11 19 8 16 2 26 20 43 4 7 43 42 15 19 40 14 31 24 39 16 13 23 19...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 52
result:
ok
Test #13:
score: 0
Accepted
time: 7ms
memory: 26168kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 1998 25 16 15 17 25 1 7 36 24 40 30 2 34 13 38 39 33 1 5 4 3 37 36 17 41 29 21 29 19 12 2 38 18 2 42 11 40 39 21 18 43 26 9 10 11 36 36 38 12 13 8 28 23 26 3 44 32 33 18 15 15 27 18 9 25 36 16 27 4 30 10 26 35 27 43 5 29 33 8 14 43 42 6 12 34 6 28 22 30 3 24 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 49
result:
ok
Test #14:
score: 0
Accepted
time: 11ms
memory: 26144kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 1999 4 5 1 2 5 4 4 4 2 5 3 5 3 3 1 2 5 5 2 3 3 2 2 4 5 3 4 3 2 1 4 2 3 5 2 2 2 5 4 3 5 1 4 2 5 4 3 2 5 3 4 3 5 2 1 1 4 3 2 5 2 1 5 3 5 3 2 4 5 4 1 2 1 2 1 4 3 5 5 2 1 3 3 4 4 4 2 5 4 2 1 2 4 2 5 3 1 1 4 2 3 4 5 2 5 1 3 3 1 2 2 5 1 5 5 4 4 3 2 2 5 4 1 2 3 1 5 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 378
result:
ok
Test #15:
score: 0
Accepted
time: 2ms
memory: 26324kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 1999 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 1
result:
ok
Test #16:
score: 0
Accepted
time: 3ms
memory: 26292kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 1997 831 845 694 533 66 466 615 401 522 181 171 87 245 250 581 66 257 441 723 212 992 910 126 106 798 939 845 214 654 754 761 109 684 708 167 693 44 255 492 586 122 295 637 565 827 487 436 630 97 454 117 814 403 306 637 822 223 327 105 95 996 416 650 181 917 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 261
result:
ok
Test #17:
score: 0
Accepted
time: 3ms
memory: 26188kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 1998 696 737 209 283 554 1052 842 822 892 502 136 1036 301 8 855 900 228 338 233 954 326 410 770 850 455 582 579 993 213 319 562 894 541 947 1010 14 743 908 277 859 458 763 463 816 923 585 880 618 352 622 780 619 11 429 133 180 258 139 807 753 350 197 616 471...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 398
result:
ok
Test #18:
score: 0
Accepted
time: 2ms
memory: 26284kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 1997 657 1176 941 515 903 1021 551 1103 491 661 1188 961 1073 923 78 355 1094 1112 1092 1006 1243 297 92 1052 223 1005 61 123 116 771 250 1080 874 1238 1046 128 360 1119 212 451 1173 13 303 443 303 1198 119 467 361 1168 784 1062 369 685 366 126 436 272 1141 8...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 29
result:
ok
Test #19:
score: 0
Accepted
time: 5ms
memory: 26224kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 1997 1079 227 1250 808 655 731 548 961 966 324 922 1264 376 203 925 805 692 1086 186 832 399 817 899 917 317 1056 737 246 936 180 90 1277 375 790 1006 934 1055 24 1138 1017 265 601 970 1160 600 994 262 340 20 1197 889 1251 885 522 106 972 602 616 990 332 1159...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 30
result:
ok
Subtask #3:
score: 0
Wrong Answer
Test #20:
score: 7
Accepted
time: 527ms
memory: 51516kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 499996 53 78 81 111 119 124 126 130 164 175 219 227 233 249 282 298 332 341 348 436 437 448 452 455 462 465 495 535 557 558 576 600 620 627 632 642 643 659 695 696 713 730 743 805 816 865 869 872 875 882 883 902 924 937 990 998 1025 1092 1137 1145 1166 1176 1...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 8
result:
ok
Test #21:
score: 0
Accepted
time: 549ms
memory: 50948kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 499996 5 7 11 19 19 19 19 23 23 27 29 31 32 33 34 37 37 40 45 49 53 57 67 69 70 76 79 80 82 82 84 89 91 96 105 109 109 109 110 111 112 113 116 119 120 121 122 129 133 135 136 142 145 147 148 151 155 160 161 162 162 171 174 177 178 179 180 181 185 189 191 192 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 9
result:
ok
Test #22:
score: -7
Wrong Answer
time: 479ms
memory: 43836kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 500000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 67862
result:
wrong answer 1st lines differ - on the 1st token, expected: '100281', found: '67862'
Subtask #4:
score: 12
Accepted
Test #28:
score: 12
Accepted
time: 495ms
memory: 43900kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 499999 2 1 2 2 2 1 2 3 1 3 1 2 2 1 2 1 1 2 1 1 2 1 1 2 1 2 1 1 1 1 1 2 2 1 1 2 1 1 1 2 1 2 1 1 1 2 3 3 3 3 1 3 1 2 2 1 1 1 3 1 3 1 1 2 1 2 2 2 1 3 2 1 1 1 2 2 1 2 2 3 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2 2 1 1 1 1 2 2 1 1 1 1 1 2 1 1 2 1 1 3 2 1 1 1 3 1 1 2 1 3 1 1 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 277713
result:
ok
Test #29:
score: 0
Accepted
time: 501ms
memory: 44696kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 499999 2 3 1 3 3 3 1 2 3 3 3 2 2 1 1 3 1 2 1 3 3 3 2 2 2 2 3 3 2 2 2 1 1 2 3 3 1 3 1 1 2 3 3 1 1 1 2 1 1 1 2 3 2 2 1 2 1 1 3 1 1 1 3 1 1 2 1 3 2 3 1 3 1 3 3 2 1 3 1 2 1 3 2 1 1 2 3 1 2 1 3 3 1 2 1 3 3 3 2 3 2 1 1 2 1 2 3 1 1 2 2 1 3 2 3 2 3 2 2 1 3 2 3 1 3 3 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 166105
result:
ok
Test #30:
score: 0
Accepted
time: 508ms
memory: 45336kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 499997 3 1 2 1 1 1 1 3 2 1 2 2 3 2 2 3 3 3 3 3 1 1 2 1 3 2 1 1 2 2 3 1 1 2 1 3 2 2 1 2 1 3 3 2 2 1 3 1 3 2 2 3 3 2 3 1 2 3 2 1 3 2 2 1 3 2 3 2 1 3 3 1 2 1 1 2 1 2 3 1 2 3 1 3 2 3 3 1 3 1 2 1 3 2 1 3 1 2 1 2 2 1 1 2 2 1 3 3 2 3 1 3 3 3 2 1 1 2 2 2 1 1 2 1 1 2 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 167067
result:
ok
Test #31:
score: 0
Accepted
time: 487ms
memory: 45024kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 499996 3 2 3 3 3 1 2 3 2 2 2 2 2 2 2 3 2 2 3 1 3 1 3 2 1 2 2 3 3 3 3 1 2 1 2 2 3 2 2 2 3 3 2 2 2 1 2 2 2 3 3 2 3 3 3 3 3 2 1 3 3 2 3 3 3 3 2 2 3 3 2 1 2 2 3 3 2 3 1 1 3 2 3 2 1 3 3 2 3 3 3 1 3 2 2 3 3 2 2 3 2 3 3 2 3 3 3 2 1 1 3 3 1 2 3 3 1 3 2 3 3 3 3 3 3 2 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 277892
result:
ok
Test #32:
score: 0
Accepted
time: 486ms
memory: 44544kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 500000 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 125000
result:
ok
Subtask #5:
score: 0
Wrong Answer
Test #33:
score: 0
Wrong Answer
time: 766ms
memory: 58044kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 499999 490225 471440 499001 369862 494577 479599 486292 476071 471988 486939 482356 482290 497141 488452 495446 494292 404798 493826 482595 481107 447196 477441 418064 495941 448927 483365 418585 489220 443224 482574 487957 467944 493253 472016 475543 442250 ...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 2
result:
wrong answer 1st lines differ - on the 1st token, expected: '1', found: '2'
Subtask #6:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #41:
score: 0
Wrong Answer
time: 111ms
memory: 28144kb
input:
8wq90di9812978rqwiok0k0o21klklm21oiwi121 79997 36415 18516 420 60790 49058 32960 27785 69895 74029 21962 53361 43308 54680 77334 61363 1780 62171 23208 1130 78835 79364 37259 45646 54570 72797 56842 34418 10553 28532 11521 52797 29973 58123 42899 62212 289 4565 10345 73305 14960 70036 68229 4746 966...
output:
nfp39szm23aa01pcmyosi03slwpeksnfjri3opqp OK 5
result:
wrong answer 1st lines differ - on the 1st token, expected: '4', found: '5'
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%