Submission #633799

#	Time	Username	Problem	Language	Result	Execution time	Memory
633799		gs14004	Swap Swap Sort (CCO21_day1problem1)	C++17	6 / 25	5040 ms	6348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int mod = 1e9 + 7;
const int MAXN = 100005;

struct bit{
	int tree[MAXN];
	void add(int x, int v){
		for(int i = x; i < MAXN; i += i & -i) tree[i] += v;
	}
	int query(int x){
		int ret = 0;
		for(int i = x; i; i -= i & -i) ret += tree[i];
		return ret;
	}
}bit;

vector<int> v[MAXN];

lint query(int x, int y){
	int j = 0;
	lint ret = 0;
	for(int i = 0; i < sz(v[y]); i++){
		while(j < sz(v[x]) && v[x][j] < v[y][i]) j++;
		ret += j;
	}
	j = 0;
	for(int i = 0; i < sz(v[x]); i++){
		while(j < sz(v[y]) && v[y][j] < v[x][i]) j++;
		ret -= j;
	}
	return ret;
}

int main(){	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, k, q; cin >> n >> k >> q;
	vector<int> ord(k); iota(all(ord), 1);
	vector<int> a(n);
	lint ret = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		ret += bit.query(k) - bit.query(a[i]);
		bit.add(a[i], 1);
		v[a[i]].push_back(i);
	}
	while(q--){
		int x; cin >> x;
		int l = ord[x - 1], r = ord[x];
		swap(ord[x - 1], ord[x]);
		ret += query(l, r);
		cout << ret << "\n";
	}
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 0 / 5
• Subtask 4: 0 / 14