oj.uz

Submission #854326

# Submission time Handle Problem Language Result Execution time Memory
854326 2023-09-26T19:30:38 Z Juan Swap Swap Sort (CCO21_day1problem1) C++17
25 / 25
 3690 ms 80876 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define tii tuple<int,int,int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
const int maxn = 1e5+5, INF=0x3f3f3f3f, MOD=1e9+7;

int bit[maxn];
map<pii,int> mp;
vector<int> cnt[maxn];

void upd(int x){
	for(; x<maxn; x+=x&-x) bit[x]++;
}

int query(int x){
	int rt=0;
	for(; x>0; x-=x&-x) rt+=bit[x];
	return rt;
}

int bbin(int id, int x){
	int l=0, r=cnt[id].size()-1;
	while(l<=r){
		int m = (l+r)/2;
		if(cnt[id][m]<x) l=m+1;
		else r=m-1;
	}
	return l;
}

int calc(int a, int b){
	int rt=0;

	if(cnt[a].size()<=cnt[b].size()){
		for(int x : cnt[a]){
			rt += bbin(b,x);
		}
	}
	else{
		for(int x : cnt[b]){
			rt += cnt[a].size() - bbin(a,x);
		}
	}

	return rt;
}

int32_t main(){
	int n,k,q; cin >> n >> k >> q;

	vector<int> v(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
		cnt[v[i]].push_back(i);
	}

	int ans=0;
	for(int i=0; i<n; i++){
		ans += query(k)-query(v[i]);
		upd(v[i]);
	}

	vector<int> target(k+1);
	for(int i=1; i<=k; i++) target[i]=i;
	while(q--){
		int id; cin >> id;
		int a=target[id], b=target[id+1];
		swap(target[id],target[id+1]);

		pii pr = {min(a,b),max(a,b)};

		if(mp.find(pr)==mp.end()) mp[pr] = calc(a,b);
		int& inv = mp[pr];

		int aux = cnt[a].size()*cnt[b].size()-inv;
		ans += aux-inv;
		inv = aux;

		cout << ans << '\n';
	}
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 8 ms 2908 KB Output is correct
3 Correct 9 ms 2904 KB Output is correct
4 Correct 10 ms 2904 KB Output is correct
5 Correct 10 ms 2904 KB Output is correct
6 Correct 10 ms 2908 KB Output is correct
7 Correct 10 ms 2908 KB Output is correct
8 Correct 11 ms 3160 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4452 KB Output is correct
2 Correct 18 ms 4564 KB Output is correct
3 Correct 19 ms 4696 KB Output is correct
4 Correct 20 ms 4696 KB Output is correct
5 Correct 26 ms 5208 KB Output is correct
6 Correct 25 ms 4952 KB Output is correct
7 Correct 29 ms 5972 KB Output is correct
8 Correct 33 ms 7248 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1348 ms 15412 KB Output is correct
2 Correct 1372 ms 15540 KB Output is correct
3 Correct 1474 ms 15344 KB Output is correct
4 Correct 1702 ms 15900 KB Output is correct
5 Correct 1824 ms 17792 KB Output is correct
6 Correct 1786 ms 17868 KB Output is correct
7 Correct 1759 ms 17796 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 8 ms 2908 KB Output is correct
3 Correct 9 ms 2904 KB Output is correct
4 Correct 10 ms 2904 KB Output is correct
5 Correct 10 ms 2904 KB Output is correct
6 Correct 10 ms 2908 KB Output is correct
7 Correct 10 ms 2908 KB Output is correct
8 Correct 11 ms 3160 KB Output is correct
9 Correct 16 ms 4452 KB Output is correct
10 Correct 18 ms 4564 KB Output is correct
11 Correct 19 ms 4696 KB Output is correct
12 Correct 20 ms 4696 KB Output is correct
13 Correct 26 ms 5208 KB Output is correct
14 Correct 25 ms 4952 KB Output is correct
15 Correct 29 ms 5972 KB Output is correct
16 Correct 33 ms 7248 KB Output is correct
17 Correct 1348 ms 15412 KB Output is correct
18 Correct 1372 ms 15540 KB Output is correct
19 Correct 1474 ms 15344 KB Output is correct
20 Correct 1702 ms 15900 KB Output is correct
21 Correct 1824 ms 17792 KB Output is correct
22 Correct 1786 ms 17868 KB Output is correct
23 Correct 1759 ms 17796 KB Output is correct
24 Correct 1757 ms 18704 KB Output is correct
25 Correct 1797 ms 19764 KB Output is correct
26 Correct 1810 ms 22568 KB Output is correct
27 Correct 1933 ms 25292 KB Output is correct
28 Correct 2029 ms 28828 KB Output is correct
29 Correct 2121 ms 35532 KB Output is correct
30 Correct 2267 ms 42092 KB Output is correct
31 Correct 2290 ms 42388 KB Output is correct
32 Correct 2048 ms 80784 KB Output is correct
33 Correct 2052 ms 19312 KB Output is correct
34 Correct 2070 ms 20408 KB Output is correct
35 Correct 2123 ms 22672 KB Output is correct
36 Correct 2466 ms 32700 KB Output is correct
37 Correct 3553 ms 77660 KB Output is correct
38 Correct 3177 ms 78244 KB Output is correct
39 Correct 2833 ms 80876 KB Output is correct
40 Correct 2471 ms 55536 KB Output is correct
41 Correct 2354 ms 61460 KB Output is correct
42 Correct 2146 ms 80140 KB Output is correct
43 Correct 2201 ms 79532 KB Output is correct
44 Correct 2292 ms 80468 KB Output is correct
45 Correct 2229 ms 80300 KB Output is correct
46 Correct 2405 ms 56508 KB Output is correct
47 Correct 2665 ms 64012 KB Output is correct
48 Correct 3690 ms 80436 KB Output is correct
49 Correct 3398 ms 79116 KB Output is correct
50 Correct 2096 ms 80380 KB Output is correct
51 Correct 1996 ms 80020 KB Output is correct
52 Correct 2005 ms 79952 KB Output is correct
53 Correct 2115 ms 80344 KB Output is correct
54 Correct 2152 ms 80168 KB Output is correct
55 Correct 1 ms 2648 KB Output is correct