제출 #1321772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1321772		Thanhs	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	685 ms	174648 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

#define name "TENBAI"
#define fi first
#define se second
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 2e5 + 5;

int a[NM], n;
long long ans;
map<int, queue<int>> mp;
vector<int> va[NM], dt[NM];

void fupd(int x, int y)
{
	for (; x < NM; x += x & -x)
		va[x].push_back(y);
}

void upd(int x, int y)
{
	for (; x < NM; x += x & -x)
		for (int i = upper_bound(all(va[x]), y) - va[x].begin(); i <= (int)va[x].size(); i += i & -i)
			dt[x][i - 1]++;
}

int get(int x, int y)
{
	int res = 0;
	for (; x; x -= x & -x)
		for (int i = upper_bound(all(va[x]), y) - va[x].begin(); i; i -= i & -i)
			res += dt[x][i - 1];
	return res;
}

long long count_swaps(std::vector<int> s) {
	n = s.size();
	for (int i = 1; i <= n; i++)
		a[i] = s[i - 1];
	vector<pair<int, int>> v;
	for (int i = 1; i <= n; i++)
	{
		int t = a[i];
		if (mp[-t].size())
		{
			if (t < 0)
				ans++;
			v.push_back({mp[-t].front(), i});
			mp[-t].pop();
		}
		else
			mp[t].push(i);
	}
	for (auto t : v)
		fupd(t.fi, t.se);
	for (int i = 1; i < NM; i++)
	{
		sort(all(va[i])), va[i].erase(unique(all(va[i])), va[i].end());
		dt[i].resize(va[i].size());
	}
	ans += 1ll * (n / 2) * (n / 2 - 1) / 2;
	for (auto t : v)
		upd(t.fi, t.se);
	for (auto t : v)
		ans += get(t.se, t.se) - get(t.fi - 1, t.se) - get(t.se, t.fi - 1) - 1;
	return ans;
}

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