QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#182720 | #6701. BaoBao Loves Reading | ucup-team004 | AC ✓ | 101ms | 4792kb | C++20 | 1.8kb | 2023-09-18 14:30:35 | 2023-09-18 14:30:35 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
template <typename T>
struct Fenwick {
int n;
std::vector<T> a;
Fenwick(int n = 0) {
init(n);
}
void init(int n) {
this->n = n;
a.assign(n, T());
}
void add(int x, T v) {
for (int i = x + 1; i <= n; i += i & -i) {
a[i - 1] += v;
}
}
T sum(int x) {
auto ans = T();
for (int i = x; i > 0; i -= i & -i) {
ans += a[i - 1];
}
return ans;
}
T rangeSum(int l, int r) {
return sum(r) - sum(l);
}
int kth(T k) {
int x = 0;
for (int i = 1 << std::__lg(n); i; i /= 2) {
if (x + i <= n && k >= a[x + i - 1]) {
x += i;
k -= a[x - 1];
}
}
return x;
}
};
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
a[i]--;
}
Fenwick<int> fen(n);
std::vector<int> ans(n + 1);
std::vector<int> lst(n, -1);
for (int i = 0; i < n; i++) {
if (lst[a[i]] == -1) {
ans[n]++;
} else {
ans[fen.rangeSum(lst[a[i]], i) - 1]++;
fen.add(lst[a[i]], -1);
}
lst[a[i]] = i;
fen.add(i, 1);
}
for (int i = n - 1; i >= 1; i--) {
ans[i] += ans[i + 1];
}
for (int i = 1; i <= n; i++) {
std::cout << ans[i] << " \n"[i == n];
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
input:
1 7 4 3 4 2 3 1 4
output:
7 6 5 4 4 4 4
result:
ok single line: '7 6 5 4 4 4 4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
100 73 45 45 2 2 2 45 35 45 16 35 16 45 35 2 16 16 45 2 45 45 16 35 35 16 35 35 2 2 2 35 45 35 45 35 16 35 2 2 16 35 16 45 45 16 45 2 16 16 35 16 45 16 45 45 16 16 35 35 35 35 45 45 45 35 16 16 16 2 16 16 35 16 2 83 78 52 7 35 33 82 51 27 45 34 17 51 55 25 26 11 52 41 25 41 13 46 33 83 83 7 40 51 33...
output:
51 30 17 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 80 77 74 73 69 68 66 64 61 61 59 56 53 49 47 47 44 42 39 38 36 36 34 33 30 29 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 2...
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 101ms
memory: 4792kb
input:
1117 72 27 62 37 62 21 71 27 62 37 37 21 21 62 71 27 37 62 37 21 71 27 21 27 71 71 62 71 62 62 37 27 37 71 62 62 37 71 62 71 71 37 27 21 71 21 27 27 62 27 71 62 21 27 37 21 21 71 37 21 37 21 37 27 21 71 62 37 37 62 37 21 27 88 58 48 19 47 46 50 4 78 11 68 80 29 4 3 88 49 54 25 78 47 78 45 34 54 4 46...
output:
63 49 36 23 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 86 84 83 82 81 78 75 72 71 69 65 64 62 60 60 59 57 53 53 52 50 48 46 45 44 42 42 41 40 40 40 40 39 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38...
result:
ok 1117 lines