#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Fenwick {
int n;
int tree[100002];
void add(int x, int y){
while(x<=n){
tree[x] += y;
x += x&-x;
}
}
int sum(int x){
int ret = 0;
while(x){
ret += tree[x];
x -= x&-x;
}
return ret;
}
} fenwick;
unordered_map<int, int> tree[400002];
void init(int i, int l, int r, int *A){
for(int j=l; j<=r; j++) tree[i][A[j]]++;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
}
ll query(int i, int l, int r, int A, int B){ /// A �����ʿ� �ִ� B�� ����
if(!tree[i][A] && !tree[i][B]) return 0;
if(r-l==1) return tree[i*2][A] * tree[i*2+1][B];
int m = (l+r)>>1;
return ll(tree[i*2][A]) * tree[i*2+1][B] + query(i*2, l, m, A, B) + query(i*2+1, m+1, r, A, B);
}
int n, k, q;
int arr[100002], perm[100002];
ll cnt[100002];
unordered_map<ll, ll> mapped;
ll ans;
ll query(int A, int B){
ll key = A * 1000000000LL + B;
if(mapped[key]) return mapped[key] - 1;
ll tmp = query(1, 1, n, A, B);
mapped[key] = tmp + 1;
return tmp;
}
int main(){
scanf("%d %d %d", &n, &k, &q);
for(int i=1; i<=n; i++){
scanf("%d", &arr[i]);
cnt[arr[i]]++;
}
if(q > 5000) n = 10000;
init(1, 1, n, arr);
for(int i=1; i<=k; i++) perm[i] = i;
fenwick.n = k;
for(int i=1; i<=n; i++){
ans += (i-1) - fenwick.sum(arr[i]);
fenwick.add(arr[i], 1);
}
for(int i=1; i<=q; i++){
int x;
scanf("%d", &x);
ll tmp = query(perm[x+1], perm[x]);
ans += cnt[perm[x+1]] * cnt[perm[x]] - tmp*2;
swap(perm[x+1], perm[x]);
printf("%lld\n", ans);
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d %d %d", &n, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
Main.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
44740 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
44740 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
