Submission #1152633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152633		the_coding_pooh	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	38 ms	67656 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 = 1e5 + 5;

deque <int> r_pos[SIZE];

long long pre[SIZE];

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));
	long long ret = 0;
	for (auto i : event){
		if(i.sc == 1){
			if(i.fs != 0)
				pre[i.fs] = pre[i.fs - 1] + 1;
			else
				pre[i.fs] = 1;
		}
		else{
			ret += pre[i.fs - 1] - pre[-i.sc];
			pre[i.fs] = pre[i.fs - 1] - 1;
		}
	}
	uwu ret;
}

long long BITree[SIZE];

void add(int pos){
	for (pos = SIZE - pos; pos < SIZE; pos += (pos & -pos)){
		BITree[pos]++;
	}
	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_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));
	long long ret = 0;
	for (auto i : event){
		if(i.sc != 1){
			ret += query(-i.sc);
			add(-i.sc);
		}
	}
	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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15