QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#567201 | #9313. Make Max | Inverted_Tuna | WA | 85ms | 10576kb | C++17 | 2.9kb | 2024-09-16 09:56:58 | 2024-09-16 09:57:05 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
struct DSU {
std::vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
std::vector<int> L(n, -1), R(n, -1);
DSU dsu(n);
for (int i = 0, j = 0; i < n; i = j) {
while (j < n && a[i] == a[j]) {
j++;
}
for (int k = i; k < j; k++) {
dsu.merge(i, k);
}
}
for (int i = 0; i < n; i++) {
if (i && dsu.find(i) != dsu.find(i - 1)) {
L[dsu.find(i)] = dsu.find(i - 1);
}
if (i != n - 1 && dsu.find(i) != dsu.find(i + 1)) {
R[dsu.find(i)] = dsu.find(i + 1);
}
}
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;
for (int i = 0; i < n; i++) {
if (dsu.find(i) == i) {
pq.emplace(a[i], i);
}
}
i64 ans = 0;
while (pq.size() > 1) {
auto [x, y] = pq.top();
pq.pop();
if (dsu.find(y) != y) {
continue;
}
ans += dsu.size(y);
// std::cerr << y + 1 << " " << dsu.size(y) << " X \n";
if (L[y] != -1 && R[y] != -1) {
if (a[L[y]] < a[R[y]]) {
//向 L 合并
R[L[y]] = R[y];
dsu.merge(L[y], y);
} else if (a[L[y]] > a[R[y]]) {
//向 R 合并
L[R[y]] = L[y];
dsu.merge(R[y], y);
} else {
//向 LR 合并
int l = L[L[y]];
int r = R[R[y]];
dsu.merge(R[y], y);
dsu.merge(R[y], L[y]);
L[dsu.find(y)] = l;
R[dsu.find(y)] = r;
}
} else if (L[y] != -1) {
R[L[y]] = R[y];
dsu.merge(L[y], y);
} else if (R[y] != -1) {
L[R[y]] = L[y];
dsu.merge(R[y], y);
}
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
4 2 1 2 2 2 2 7 1 1 1 2 2 2 2 3 1 2 3
output:
1 0 3 3
result:
ok 4 number(s): "1 0 3 3"
Test #2:
score: 0
Accepted
time: 84ms
memory: 10576kb
input:
2 198018 875421126 585870339 471894633 383529988 625397685 944061047 704695631 105113224 459022561 760848605 980735314 847376362 980571959 329939331 644635272 326439858 752879510 837384394 175179068 182094523 397239381 1199016 185143405 279638454 252374970 822030887 860312140 137248166 993229443 164...
output:
4084978 4130372
result:
ok 2 number(s): "4084978 4130372"
Test #3:
score: -100
Wrong Answer
time: 85ms
memory: 10524kb
input:
2 195768 3086 1582 7854 5577 5243 2734 8054 4805 5686 7065 5555 2410 6240 7589 2889 3745 8094 9147 9438 1252 5497 5786 6655 4437 3933 2579 5722 9512 3117 1742 5362 2068 1853 4069 9231 1126 3991 420 2571 5517 3063 7279 8085 6111 5503 5980 50 6003 244 9684 6343 6517 1598 5223 5520 982 3932 1093 1149 7...
output:
2562676 2567092
result:
wrong answer 1st numbers differ - expected: '3061429', found: '2562676'