제출 #992018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992018		coolboy19521	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	526 ms	149200 KiB

shoes

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

using namespace std;

const int sz = 2e5 + 10;

int st[sz * 4];

int query(int ql, int qr, int le, int ri, int v) {
	if (le > qr || ri < ql) return 0;
	if (ql <= le && ri <= qr) return st[v];

	int mi = le + (ri - le) / 2;
	int ls = query(ql, qr, le, mi, v * 2);
	int rs = query(ql, qr, mi + 1, ri, v * 2 + 1);

	return ls + rs;
}

void update(int le, int ri, int k, int v) {
	if (le == k && ri == k) {
		st[v] = 1;
	} else if (le <= k && k <= ri) {
		int mi = le + (ri - le) / 2;
		update(le, mi, k, v * 2);
		update(mi + 1, ri, k, v * 2 + 1);

		// cout << "UPD RANGE: " << le << ' ' << ri << '\n';

		st[v] = st[v * 2] + st[v * 2 + 1];
	}
}

long long count_swaps(std::vector<int> s) {
	map<int,queue<int>>cl;
	int n = s.size();

	for (int i = 0; i < n; i ++) {
		cl[s[i]].push(i);
	}

	long long r = 0;

	for (int i = 0; i < n; i ++) {
		auto it = query(i + 1, i + 1, 1, n, 1);
		if (it != 0) continue;

		int ix = cl[-s[i]].front();
		int vs = i - query(1, i + 1, 1, n, 1);
		int ve = ix - query(1, ix + 1, 1, n, 1);

		// cout << vs << ' ' << ve << '\n';

		r += (ve - vs);

		if (s[i] < 0) {
			r --;
		}

		cl[-s[i]].pop();
		cl[s[i]].pop();

		// cout << "IND " << i << ' ' << vs << '\n';
		// update(i + 1, i + 1, 1, n, 1);
		update(1, n, i + 1, 1);
		// cout << "IND " << ix << ' ' << ve << '\n';
		update(1, n, ix + 1, 1);
		// update(ix + 1, ix + 1, 1, n, 1);
		// cout << i << ' ' << ix << '\n';
		// cout << "SUM OF ALL: " << query(1, n, 1, n, 1) << '\n';
	}

	return r;
}

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