QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #689693 | #9477. Topological Sort | ucup-team3215# | AC ✓ | 12ms | 5928kb | C++23 | 588b | 2024-10-30 18:12:17 | 2024-10-30 18:12:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 1, mod = 998244353;
int p2[N];
int main() {
cin.tie(0)->sync_with_stdio(0);
for (int p = 1; auto& q: p2) q = p, p = p * 2 % mod;
int n; cin >> n;
vector<array<int, 2>> v;
int ans = 1;
for (int x, i = 0; i < n; ++i) {
cin >> x;
while (v.size() && v.back()[1] < x) v.pop_back();
if (v.empty()) ans = ans * (uint64_t)p2[i] % mod;
else ans = ans * (uint64_t)p2[v.back()[0]] % mod * (p2[i - v.back()[0]] + mod - 1) % mod;
v.push_back({i, x});
}
cout << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4584kb
input:
3 1 3 2
output:
4
result:
ok "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 4296kb
input:
5 1 2 3 4 5
output:
1024
result:
ok "1024"
Test #3:
score: 0
Accepted
time: 1ms
memory: 4324kb
input:
6 4 2 1 5 6 3
output:
4096
result:
ok "4096"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4328kb
input:
492 397 486 227 395 58 452 172 216 130 181 268 482 85 209 365 104 373 90 260 326 252 96 267 106 102 398 441 41 292 314 12 78 242 353 153 424 179 86 299 228 54 390 73 465 396 349 4 10 451 99 342 250 391 6 323 197 159 47 136 473 392 77 125 362 418 255 291 13 238 339 8 28 413 121 384 157 152 23 221 305...
output:
73428942
result:
ok "73428942"
Test #5:
score: 0
Accepted
time: 1ms
memory: 4600kb
input:
117 114 89 34 77 56 24 36 97 57 75 25 99 51 87 31 53 20 18 71 88 92 11 101 5 105 81 113 110 86 37 79 33 61 13 9 2 48 7 63 3 45 4 74 102 38 30 23 55 115 112 44 76 35 62 10 103 21 72 106 40 68 93 22 66 50 52 17 58 78 95 116 8 91 82 65 1 47 19 15 60 27 80 26 100 6 107 117 98 16 69 83 109 12 96 111 32 2...
output:
973031884
result:
ok "973031884"
Test #6:
score: 0
Accepted
time: 0ms
memory: 4604kb
input:
142 5 91 117 42 103 25 15 68 17 57 6 108 94 139 49 61 118 130 50 36 39 135 53 113 73 16 75 134 37 124 140 93 78 105 20 136 59 48 10 9 126 99 119 1 88 86 38 69 115 62 97 55 3 85 23 82 65 84 106 83 24 31 131 109 44 11 8 33 89 125 141 112 128 122 74 22 123 2 43 129 56 111 87 34 47 100 12 71 120 81 28 2...
output:
689040121
result:
ok "689040121"
Test #7:
score: 0
Accepted
time: 0ms
memory: 4380kb
input:
2 1 2
output:
2
result:
ok "2"
Test #8:
score: 0
Accepted
time: 1ms
memory: 4616kb
input:
2 2 1
output:
1
result:
ok "1"
Test #9:
score: 0
Accepted
time: 12ms
memory: 4560kb
input:
194626 192391 66573 51175 20393 139133 182361 61827 110888 4046 131771 18067 2183 160224 138697 39109 20417 69500 109571 52869 129131 77495 95741 123039 79656 88279 149323 76536 158952 163825 12131 178853 174294 83666 103342 100664 149219 136306 81716 100831 29396 128703 43798 56614 184849 170761 14...
output:
768358540
result:
ok "768358540"
Test #10:
score: 0
Accepted
time: 10ms
memory: 4260kb
input:
160968 160947 4849 31045 8012 36591 12857 147608 10869 130042 51427 115245 84111 63736 84890 113838 132449 78264 122080 149108 37262 48513 10846 72189 77505 32035 103483 23564 51479 41991 82334 117627 43428 73435 61631 138561 135985 70663 54059 43373 79399 126360 114320 15911 898 74743 72917 118342 ...
output:
817724348
result:
ok "817724348"
Test #11:
score: 0
Accepted
time: 7ms
memory: 4604kb
input:
111001 26673 41956 62271 20608 31376 57244 96627 21050 358 38331 27722 39740 731 102706 60567 27528 93333 73599 1241 86518 49179 99721 8859 87696 39278 31105 60999 66188 41513 74527 77815 29823 43087 110 98990 78723 42526 31732 32018 1014 7403 69997 90978 55115 40241 14889 22516 102918 30682 61528 5...
output:
975779120
result:
ok "975779120"
Test #12:
score: 0
Accepted
time: 8ms
memory: 4376kb
input:
136936 37703 45931 8052 128245 66821 76075 66893 81424 116099 28846 49133 19515 107613 76522 54074 125802 23455 80819 65212 44785 118726 40345 36957 88481 82004 105105 135593 123696 16840 31807 103176 39208 58888 76782 38881 116052 74631 127015 21372 68215 97169 103724 104325 79254 100408 34321 8445...
output:
585608213
result:
ok "585608213"
Test #13:
score: 0
Accepted
time: 12ms
memory: 4372kb
input:
200000 4 3 1 2 7 6 5 8 9 16 13 11 10 12 15 14 18 17 21 20 19 22 24 23 25 28 31 32 29 30 27 26 34 36 38 35 33 37 41 40 39 42 43 50 47 46 49 44 48 45 51 54 52 53 60 62 57 59 56 58 55 61 71 64 68 63 72 66 69 65 67 70 76 78 75 77 79 80 73 74 85 86 81 87 82 83 90 88 84 89 92 93 91 97 100 98 95 96 99 101 ...
output:
835319992
result:
ok "835319992"
Test #14:
score: 0
Accepted
time: 12ms
memory: 4264kb
input:
200000 1 45 36 6 64 47 41 63 59 29 28 10 4 15 33 35 18 68 56 31 25 12 22 69 44 55 61 54 16 30 42 39 17 65 60 58 52 9 53 7 8 5 49 57 26 24 46 38 37 21 48 66 32 34 11 50 2 13 62 43 3 23 51 27 67 40 14 19 20 71 70 86 115 107 78 105 76 110 73 80 93 88 72 100 77 108 92 106 85 97 95 81 103 79 84 101 102 7...
output:
806652810
result:
ok "806652810"
Test #15:
score: 0
Accepted
time: 12ms
memory: 4976kb
input:
200000 199997 199999 200000 199998 199995 199994 199996 199993 199987 199989 199986 199992 199988 199991 199990 199985 199976 199982 199979 199980 199984 199983 199977 199978 199981 199972 199973 199975 199974 199968 199969 199970 199971 199965 199961 199958 199967 199960 199966 199962 199959 199963...
output:
634066694
result:
ok "634066694"
Test #16:
score: 0
Accepted
time: 12ms
memory: 4684kb
input:
200000 199988 199987 199997 199990 199994 199995 199999 199992 199993 199998 199991 199996 199989 200000 199971 199930 199970 199965 199972 199950 199977 199951 199945 199976 199960 199947 199982 199962 199936 199955 199985 199956 199949 199942 199952 199938 199940 199981 199935 199944 199946 199969...
output:
545252947
result:
ok "545252947"
Test #17:
score: 0
Accepted
time: 10ms
memory: 4368kb
input:
193839 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 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
74820210
result:
ok "74820210"
Test #18:
score: 0
Accepted
time: 7ms
memory: 5928kb
input:
196576 196576 196575 196574 196573 196572 196571 196570 196569 196568 196567 196566 196565 196564 196563 196562 196561 196560 196559 196558 196557 196556 196555 196554 196553 196552 196551 196550 196549 196548 196547 196546 196545 196544 196543 196542 196541 196540 196539 196538 196537 196536 196535...
output:
861096285
result:
ok "861096285"
Extra Test:
score: 0
Extra Test Passed