제출 #488284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
488284		ssense	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	124 ms	138064 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl

queue<int> q1[100005], q2[100005];

struct FenwickTree {
	vector<int> bit;  // binary indexed tree
	int n;
	FenwickTree(int n) {
		this->n = n + 1;
		bit.assign(n + 1, 0);
	}
	FenwickTree(vector<int> a)
	: FenwickTree(a.size()) {
		for (size_t i = 0; i < a.size(); i++)
		add(i, a[i]);
	}
	int sum(int idx) {
		int ret = 0;
		for (++idx; idx > 0; idx -= idx & -idx)
		ret += bit[idx];
		return ret;
	}
	int sum(int l, int r) {
		return sum(r) - sum(l - 1);
	}
	void add(int idx, int delta) {
		for (++idx; idx < n; idx += idx & -idx)
		bit[idx] += delta;
	}
};


long long count_swaps(vector<int> s)
{
	int n = s.size();
	int cnt = -1;
	for(int i = 0; i < n; i++)
	{
		if(s[i] < 0)
		{
			cnt+=2;
			q1[-s[i]].push(cnt);
			q2[-s[i]].push(cnt);
		}
	}
	for(int i = 0; i < n; i++)
	{
		if(s[i] > 0)
		{
			int prev = s[i];
			s[i] = q2[s[i]].front()+1;
			q2[prev].pop();
		}
		else
		{
			int prev = s[i];
			s[i] = q1[-s[i]].front();
			q1[-prev].pop();
		}
	}
	int ans = 0;
	FenwickTree ft(n+5);
	for(int i = 0; i < n; i++)
	{
		ans+=ft.sum(s[i] + 1, n + 1);
		ft.add(s[i], 1);
	}
	return ans;
}
/*
int main()
{
	int n;
	cin >> n;
	vint a(2*n);
	for(int i = 0; i < 2*n; i++)
	{
		cin >> a[i];
	}
	cout << count_swaps(a);
}
*/
/*
3
-2 -2 -1 2 1 2
 -2 -2 2 -1 1 2
 */

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