Submission #14019

#	Time	Username	Problem	Language	Result	Execution time	Memory
14019		pjsdream	버블 정렬 (OJUZ10_bubblesort)	C++14	100 / 100	85 ms	6552 KiB

bubblesort

#pragma warning(disable:4996)

#include <stdio.h>
#include <algorithm>
using namespace std;

int n, k;
int a[100000];
int v[100000];
pair<int, int> p[100000];

int ts;
int t1[400000];
int t2[400000];

int cnt[100000];

int ans[100000];

int mymin(int a, int b) { return a<b?a:b; }
int mymax(int a, int b) { return a>b?a:b; }

int t1find(int l, int r)
{
	int res=0;

	for (l+=ts, r+=ts; l<=r; l/=2, r/=2) {
		if (l&1) {
			res += t1[l];
			l++;
		}
		if (!(r&1)) {
			res += t1[r];
			r--;
		}
	}

	return res;
}

void t1insert(int x)
{
	for (x+=ts; x; x/=2)
		t1[x]++;
}

int t2find(int k)
{
	int p = 1;
	while (p < ts) {
		int l = p*2;
		int r = l+1;

		if (r >= ts+n || k < t2[l]) {
			p = l;
		}
		else {
			k -= t2[l];
			p = r;
		}
	}

	return p - ts;
}

void t2erase(int x)
{
	for (x+=ts; x; x/=2)
		t2[x]--;
}

int main ()
{
	scanf("%d%d", &n, &k);
	for (int i=0; i<n; i++)
		scanf("%d", &a[i]), p[i] = make_pair(a[i], i);

	sort(p, p+n);
	for (int i=0; i<n; i++) {
		if (i && p[i].first == p[i-1].first)
			v[p[i].second] = v[p[i-1].second];
		else v[p[i].second] = i;
	}

	for (ts=1; ts<n; ts*=2);

	for (int i=0; i<n; i++) {
		cnt[i] = mymax(t1find(v[i]+1, n-1) - k, 0);
		t1insert(v[i]);
	}

	for (int i=0; i<n; i++) t2[ts+i] = 1;
	for (int i=ts-1; i>=1; i--) {
		int l = i*2;
		int r = l+1;

		if (l < ts+n) t2[i] += t2[l];
		if (r < ts+n) t2[i] += t2[r];
	}

	for (int i=0; i<n; i++) {
		int id = t2find(cnt[ p[i].second ]);
		ans[id] = p[i].first;
		t2erase(id);
	}

	for (int i=0; i<n; i++) printf("%d ", ans[i]);
	printf("\n");

	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 47 / 47
• Subtask 4: 19 / 19