이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
int B = 100;
vector<int> occ[100008];
int a[100008], p[100008];
vector<long long> f[1008];
int Hrank[100008], pf[100008];
long long res; int pt;
long long query(int x, int y) { // #yx - #xy = -(#x*#y) + 2#yx = #x*#y - 2#xy
if (occ[x].size() >= B) return -1LL * occ[x].size() * occ[y].size() + 2 * f[Hrank[x]][y];
if (occ[y].size() >= B) return 1LL * occ[x].size() * occ[y].size() - 2 * f[Hrank[y]][x];
res = 0; pt = -1;
for (int o_x : occ[x]) {
while (pt + 1 < occ[y].size() && occ[y][pt + 1] < o_x) ++pt;
res -= pt + 1;
}
pt = -1;
for (int o_y : occ[y]) {
while (pt + 1 < occ[x].size() && occ[x][pt + 1] < o_y) ++pt;
res += pt + 1;
}
return res;
}
struct Binary_Indexed_Tree {
vector<int> BIT; int n;
Binary_Indexed_Tree(int n) : n(n) {BIT.assign(n + 8, 0);}
Binary_Indexed_Tree() {}
int pt, res;
void update(int u) {
pt = u;
while (pt <= n) {
++BIT[pt];
pt += pt & -pt;
}
}
int pf(int p) {
if (p <= 0) return 0;
pt = p; res = 0;
while (pt) {
res += BIT[pt];
pt -= pt & -pt;
}
return res;
}
int range(int l, int r) {
if (l > r) return 0;
return pf(r) - pf(l - 1);
}
};
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, k, q, x; cin >> n >> k >> q;
for (int i = 1; i <= n; ++i) cin >> a[i], occ[a[i]].push_back(i);
iota(p + 1, p + n + 1, 1); long long inv = 0;
Binary_Indexed_Tree tree(k);
for (int i = 1; i <= n; ++i) inv += tree.range(a[i] + 1, k), tree.update(a[i]);
int m = 0;
for (x = 1; x <= k; ++x) if (occ[x].size() >= B) {
++m; Hrank[x] = m;
for (int i = 1; i <= n; ++i) pf[i] = pf[i - 1] + (a[i] == x);
f[Hrank[x]].resize(k + 1);
for (int i = 1; i <= n; ++i) f[Hrank[x]][a[i]] += (a[i] != x ? pf[i] : 0);
}
while (q--) {
cin >> x; swap(p[x], p[x + 1]);
inv += query(p[x + 1], p[x]);
cout << inv << '\n';
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'long long int query(int, int)':
Main.cpp:15:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
15 | if (occ[x].size() >= B) return -1LL * occ[x].size() * occ[y].size() + 2 * f[Hrank[x]][y];
| ~~~~~~~~~~~~~~^~~~
Main.cpp:16:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
16 | if (occ[y].size() >= B) return 1LL * occ[x].size() * occ[y].size() - 2 * f[Hrank[y]][x];
| ~~~~~~~~~~~~~~^~~~
Main.cpp:19:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | while (pt + 1 < occ[y].size() && occ[y][pt + 1] < o_x) ++pt;
| ~~~~~~~^~~~~~~~~~~~~~~
Main.cpp:24:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | while (pt + 1 < occ[x].size() && occ[x][pt + 1] < o_y) ++pt;
| ~~~~~~~^~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:71:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
71 | for (x = 1; x <= k; ++x) if (occ[x].size() >= B) {
| ~~~~~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |