Submission #1288270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288270		muhammad-ahmad	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	463 ms	149636 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

const int N = 2e5 + 5;
int T[4 * N], a[N], n, m;
 
void build(int s = 0, int e = n, int v = 1){
	if (e - s == 1){
		T[v] = a[s];
		return;
	}
	int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
	build(s, mid, lc);
	build(mid, e, rc);
	T[v] = T[lc] + T[rc];
}
 
int query(int l, int r, int s = 0, int e = n, int v = 1){
	if (l <= s && e <= r){
		return T[v];
	}
	
	int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
	
	if (r > mid){
		int ans = query(l, r, mid, e, rc);
		if (l < mid) ans += query(l , r, s, mid, lc);
		return ans;
	}
	else return query(l , r, s, mid, lc);
}
 
void update(int val, int idx, int s = 0, int e = n, int v = 1){
	if (idx < s or idx >= e) return;	
	if (e - s == 1){
		T[v] = val;
		return;
	}
	int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
	update(val, idx, s, mid, lc);
	update(val, idx, mid, e, rc);
	T[v] = T[lc] + T[rc];
}
 

long long count_swaps(vector<int> s) {
	n = s.size();
	for (int i = 0; i < n; i++) a[i] = 1;
	build();
	
	
	map<int, deque<int>> C;
	for (int i = 0; i < n; i++){
		s[i] *= -1;
		C[-s[i]].push_back(i);
	}	
	
	int vis[n] = {};
	long long ans = 0;
	
	for (int i = 0; i < n; i++){
		if (vis[i]) continue;
		int idx = C[s[i]].front();
		vis[i] = vis[idx] = 1;
		C[s[i]].pop_front();
		C[-s[i]].pop_front();
		
		update(0, i);
		update(0, idx);
		
		
		// cout << i << ' ' << idx << endl;
		
		int v = query(i, idx);
		// int v = 1;
		ans += v + (s[i] < 0);
	}
	
	return ans;
}

// int main(){
	// cout << count_swaps({2, 1, -1, -2});
// }

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15