Submission #774961

#	Time	Username	Problem	Language	Result	Execution time	Memory
774961		vjudge1	Swap Swap Sort (CCO21_day1problem1)	C++17	0 / 25	145 ms	24984 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005 
#define int long long

const int modulo = 1e9 + 7, S = 300;


int table[N];

void update(int pos, int val){
	while(pos < N){
		table[pos] += val;
		int lsb = pos & -pos;
		pos += lsb;
	}
}

int query(int pos){
	int ans = 0;
	while(pos > 0){
		ans += table[pos];
		int lsb = pos & -pos;
		pos -= lsb;
	}
	return ans;
}



int32_t main(){
	//fileio();
	fastio();


	int n, k, q;
	cin>>n>>k>>q;
	vector<int> arr(n + 5, 0);
	vector<int> pre[n + 5], ind[n + 5];
	map<int, int> done[k + 5], val[k + 5];
	for (int i = 1; i <= n; i++){
		cin>>arr[i];
		ind[arr[i]].pb(i);
	}


	int ans = 0;

	for (int i = k; i >= 1; i--){
		for (int j = (int)ind[i].size() - 1; j >= 0; j--)
		{
			ans += query(ind[i][j]);
			update(ind[i][j], 1);
		}
	}
	for (int i = 1; i <= k; i++){
		if (ind[i].size() >= S){
			pre[i].resize(n + 5, 0);
			for (int j = 1; j <= n; j++){
				if (arr[j] == i) pre[i][j]++;
				pre[i][j] += pre[i][j - 1];
			}
		}
	}

	vector<int> curr(k + 5, 0);
	iota(curr.begin(), curr.end(), 0);

	while(q--){
		int x;
		cin>>x;
		int a = curr[x], b = curr[x + 1];
		if (done[a][b]){
			int bk = val[a][b];
			int fr = (int)ind[a].size() * ind[b].size() - bk;
			ans += bk - fr;
			cout<<ans<<endl;
			continue;
		}
		swap(curr[x], curr[x + 1]);
		int fr = 0, bk = 0;
		int flag = 0;
		if (ind[a].size() < ind[b].size())
			swap(a, b), flag = 1;

		if (ind[a].size() >= S && ind[b].size() < S){
			for (auto i : ind[b]){
				bk += pre[a][i];
			}
		}

		else{
			int i = 0, j = 0;
			while(i < ind[a].size() && j < ind[b].size())
			{
				while(i + 1 < ind[a].size() && ind[a][i + 1] < ind[b][j]) i++;
				if (ind[a][i] < ind[b][j]) bk += i + 1;
				j++;
			}
		}
		fr = (int)ind[a].size() * ind[b].size() - bk;
		//cout<<a<<sp<<b<<sp<<fr<<sp<<bk<<endl;
		if (flag) swap(fr, bk);
		done[a][b] = 1, val[a][b] = bk;
		ans += bk - fr;
		cout<<ans<<endl;
	}



	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
} 

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:102:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |    while(i < ind[a].size() && j < ind[b].size())
      |          ~~^~~~~~~~~~~~~~~
Main.cpp:102:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |    while(i < ind[a].size() && j < ind[b].size())
      |                               ~~^~~~~~~~~~~~~~~
Main.cpp:104:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     while(i + 1 < ind[a].size() && ind[a][i + 1] < ind[b][j]) i++;
      |           ~~~~~~^~~~~~~~~~~~~~~

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