QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#664387 | #9477. Topological Sort | Zvezdy# | WA | 3ms | 16328kb | C++14 | 2.4kb | 2024-10-21 20:24:22 | 2024-10-21 20:24:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
vector<int> e[maxn];
const int inf = 1e18;
int idx = 1;
int a[maxn];
const int mod = 998244353;
int ksm(int a, int b) {
if (b <= 0) return 1;
int ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % mod;
}
a = a * a % mod;
b >>= 1;
}
return ans;
}
int lowbit(int x) {
return x & -x;
}
int tr[maxn];
void update(int x, int c) {
for (int i = x; i < maxn; i += lowbit(i)) {
tr[i] += c;
}
}
int query(int x) {
int ans = 0;
for (int i = x; i; i -= lowbit(i)) {
ans += tr[i];
}
return ans;
}
vector<int> v[maxn];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = 1;
int j = 1;
for (int i = 1; i <= n; i++) {
if (i == 1 || a[i] < a[i - 1]) {
v[j].push_back(a[i]);
ans = ans * ksm(2, (i - 2)) % mod;
} else {
v[++j].push_back(a[i]);
}
}
vector<int> fir(j + 1);
for (int i = 1; i <= j; i++) {
fir[i] = v[i][0];
reverse(v[i].begin(), v[i].end());
}
n = j;
vector<int> sum(n + 1);
vector<pair<int, int>> vec;
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + v[i].size();
vec.emplace_back(fir[i], i);
}
sort(vec.begin(), vec.end(), greater<pair<int, int>>());
auto check = [&](int mid, int i) -> bool {
return query(mid) == query(i);
};
for (auto &[fir, i] : vec) {
if (query(i) == 0) {
ans = ans * ksm(2, sum[i - 1]) % mod;
update(i, 1);
continue;
}
int l = 1, r = i;
while (l < r) {
int mid = l + r >> 1;
if (check(mid, i)) {
r = mid;
} else
l = mid + 1;
}
int j = l;
int p = upper_bound(v[j].begin(), v[j].end(), fir) - v[j].begin();
ans = ans * ((ksm(2, (p + 1)) % mod - 1 + mod) % mod) % mod;
int les = v[j].size();
les -= (p + 1);
ans = ans * (ksm(2, les)) % mod;
ans = ans * (ksm(2, sum[i - 1] - v[j].size()));
update(i, 1);
}
cout << ans << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 16096kb
input:
3 1 3 2
output:
4
result:
ok "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 16088kb
input:
5 1 2 3 4 5
output:
1024
result:
ok "1024"
Test #3:
score: 0
Accepted
time: 0ms
memory: 16328kb
input:
6 4 2 1 5 6 3
output:
4096
result:
ok "4096"
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 16132kb
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:
-165764470675238075
result:
wrong answer 1st words differ - expected: '73428942', found: '-165764470675238075'