이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false);
#define ll long long
#define pii pair<ll, ll>
#define F first
#define S second
#define pb push_back
#define SZ(x) ((ll)(x).size())
const ll N = 1e5+100, M = 5e3+100;
ll n, k, q, a[N], b[N], target[N];
vector<ll> cnt[N];
map<pii, ll> mp;
ll merge(int l, int mid, int r) {
ll p1 = l, p2 = mid, pt = l, c = 0;
while (p1 < mid && p2 < r) {
//if (l == 2 && r == 5) cout << p1 << " " << p2 << endl;
if (a[p1] <= a[p2]) {
b[pt++] = a[p1++];
c += p2 - mid;
} else {
b[pt++] = a[p2++];
}
}
//cout << p1 << " " << p2 << endl;
while (p1 < mid) {
b[pt++] = a[p1++];
c += r - mid;
}
while (p2 < mid) {
b[pt++] = a[p2++];
}
sort(a+l, a+r);
return c;
}
ll solve(int l, int r) {
if (l + 1 == r) return 0;
int mid = (l + r) / 2;
ll c = solve(l, mid) + solve(mid, r) + merge(l, mid, r);
return c;
}
ll count(int ind, int x) {
int l = 0, r = SZ(cnt[x]) - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (ind > cnt[x][mid]) l = mid + 1;
else r = mid - 1;
}
return l;
}
ll calc(int x, int y) {
ll inv = 0;
if (SZ(cnt[x]) <= SZ(cnt[y])) {
for (auto ind: cnt[x]) {
inv += count(ind, y);
}
} else {
for (auto ind: cnt[y]) {
//cout << x << " " << y << ": " << ind << " " << inv << endl;
inv += SZ(cnt[x]) - count(ind, x);
}
}
return inv;
}
int main()
{
sui
cin >> n >> k >> q;
for (int i = 0; i < n; i++) {
cin >> a[i];
b[i] = a[i];
cnt[a[i]].pb(i);
}
for (int i = 1; i <= k; i++) {
target[i] = i;
}
ll total = solve(0, n);
while (q--) {
ll j; cin >> j;
int fi = target[j], se = target[j+1];
swap(target[j], target[j+1]);
pii cur = {min(target[j], target[j+1]), max(target[j], target[j+1])};
if (mp.find(cur) == mp.end()) mp[cur] = calc(cur.F, cur.S);
int inv = mp[cur];
//cout << cur.F << " " << cur.S << " "<< inv << endl;
if (fi < se) {
total += SZ(cnt[fi]) * SZ(cnt[se]) - inv * 2;
}
else {
total += 2 * inv - SZ(cnt[fi]) * SZ(cnt[se]);
}
cout << total << endl;
}
//for (int i = 1; i <= k; i++) cout << d[i] << "-" << e[i] << " ";
return 0;
}
# | 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... |