제출 #1051590

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

shoes

#include <bits/stdc++.h>

#include "shoes.h"

#define F first
#define S second

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;

int fen[N];
stack <int> st[N];

void add(int x, int val) {for (x++; x < N; x += x & -x) fen[x] += val;}
int get(int x) {int out = 0; for (x++; x; x -= x & -x) out += fen[x]; return out;}

ll count_swaps(vector <int> a) {
	int n = a.size();
	
	vector <int> pa(2*n, -1);
	for (int i = 0; i < n; i++) {
		int x = abs(a[i]);
		if (st[x].empty()) st[x].push(i);
		else {
			if ((a[i] > 0) == (a[st[x].top()] > 0)) st[x].push(i);
			else {
				pa[st[x].top()] = i;
				st[x].pop();
			}
		}
	}
	
	ll res = 0;
	for (int i = 0; i < 2*n; i++) {
		if (pa[i] == -1) continue;
		res += pa[i]-i-(a[i] < 0) - get(pa[i])+get(i);
		add(pa[i], 1);
	}
	
	return res;
}

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