QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #201085 | #6544. Cooperation Game | ucup-team1209# | WA | 3ms | 13908kb | C++20 | 958b | 2023-10-05 10:25:57 | 2023-10-05 10:25:58 |
Judging History
answer
#include<bits/stdc++.h>
const int N = 300005;
const int mod = 1e9 + 7;
using ll = long long;
using pr = std::pair<int, int>;
using std::cin;
using std::cout;
int n, m;
std::vector<int> pos[N];
int a[N];
int match[N];
int bit[N];
int main() {
std::ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
for(int i = 1;i <= T;++i) {
cin >> n;
for(int i = 1;i <= n;++i) {
cin >> a[i], pos[a[i]].push_back(i);
}
for(int i = 1;i <= n;++i) {
for(int x = 0;x * 2 + 1 < (int) pos[a[i]].size();++x) {
match[pos[a[i]][pos[a[i]].size() - x - 1]] = pos[a[i]][x];
}
}
ll ans = 0;
for(int i = 1;i <= n;++i) if(match[i]) {
ans += i - match[i];
for(int x = match[i];x;x &= x - 1) {
ans -= bit[x];
}
for(int x = match[i];x <= n;x += x & -x) {
bit[x] += 1;
}
}
cout << ans << '\n';
for(int i = 1;i <= n;++i) {
pos[i].clear();
match[i] = 0;
bit[i] = 0;
}
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 12680kb
input:
2 7 1 2 1 1 2 1 2 12 1 2 3 1 2 3 1 2 3 1 2 3
output:
10 30
result:
ok 2 number(s): "10 30"
Test #2:
score: 0
Accepted
time: 0ms
memory: 13360kb
input:
1 7 1 2 1 1 2 1 2
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 2ms
memory: 12188kb
input:
1 12 1 2 3 1 2 3 1 2 3 1 2 3
output:
30
result:
ok 1 number(s): "30"
Test #4:
score: 0
Accepted
time: 0ms
memory: 13336kb
input:
1 5 1 1 1 1 1
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 2ms
memory: 13908kb
input:
1 5 1 2 2 2 2
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 2ms
memory: 12300kb
input:
1 5 1 2 4 1 4
output:
4
result:
ok 1 number(s): "4"
Test #7:
score: 0
Accepted
time: 3ms
memory: 12668kb
input:
1 6 6 2 3 1 5 5
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: -100
Wrong Answer
time: 2ms
memory: 13640kb
input:
1 7 3 3 4 1 2 1 7
output:
2
result:
wrong answer 1st numbers differ - expected: '3', found: '2'