Submission #1152665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152665		the_coding_pooh	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	131 ms	143536 KiB

shoes

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

#define fs first
#define sc second

#define all(x) x.begin(), x.end()

using namespace std;

const int SIZE = 2e5 + 5;

deque <int> r_pos[SIZE];

long long BITree[SIZE];

void add(int pos, int a){
	for (pos = SIZE - pos; pos < SIZE; pos += (pos & -pos)){
		BITree[pos] += a;
	}
	uwu;
}

long long query(int pos){
	long long ret = 0;
	for (pos = SIZE - pos; pos; pos -= (pos & -pos)){
		ret += BITree[pos];
	}
	uwu ret;
}

long long count_cross(vector <pair<int, int>> intv){
	vector <pair<int, int>> event;
	for(auto i:intv){
		event.push_back({i.fs, 1});
		event.push_back({i.sc, -i.fs});
	}
	sort(all(event));
	memset(BITree, 0, sizeof(BITree));
	long long ret = 0;
	for (auto i : event){
		if(i.sc == 1){
			add(i.fs, 1);
		}
		else{
			add(-i.sc, -1);
			ret += query(-i.sc);
		}
	}
	uwu ret;
}

long long count_contains(vector <pair<int, int>> intv){
	vector <pair<int, int>> event;
	for(auto i:intv){
		event.push_back({i.fs, 1});
		event.push_back({i.sc, -i.fs});
	}
	sort(all(event));
	memset(BITree, 0, sizeof(BITree));
	long long ret = 0;
	for (auto i : event){
		if(i.sc != 1){
			ret += query(-i.sc);
			add(-i.sc, 1);
		}
	}
	uwu ret;
}

long long count_swaps(vector<int> s) {
	int N = s.size() / 2;
	for (int i = 0; i < 2 * N; i++){
		if(s[i] > 0)
			r_pos[s[i]].push_back(i);
	}
	vector <pair<int, int>> team_up;
	long long lr_swap = 0;
	for (int i = 0; i < 2 * N; i++){
		if(s[i] < 0){
			team_up.push_back({i, r_pos[-s[i]].front()});
			r_pos[-s[i]].pop_front();
			if(team_up.back().sc < team_up.back().fs){
				lr_swap++;
				swap(team_up.back().fs, team_up.back().sc);
			}
		}
	}
	long long cs = count_cross(team_up), ct = count_contains(team_up);
	// cerr << lr_swap << ' ' << cs << ' ' << ct << '\n';
	uwu lr_swap + cs + 2 * ct;
}

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