oj.uz

Submission #14019

# Submission time Handle Problem Language Result Execution time Memory
14019 2015-04-25T01:51:21 Z pjsdream 버블 정렬 (OJUZ10_bubblesort) C++14
100 / 100
 85 ms 6552 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6552 KB Output is correct
2 Correct 0 ms 6552 KB Output is correct
3 Correct 0 ms 6552 KB Output is correct
4 Correct 0 ms 6552 KB Output is correct
5 Correct 0 ms 6552 KB Output is correct
6 Correct 0 ms 6552 KB Output is correct
7 Correct 0 ms 6552 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6552 KB Output is correct
2 Correct 2 ms 6552 KB Output is correct
3 Correct 0 ms 6552 KB Output is correct
4 Correct 0 ms 6552 KB Output is correct
5 Correct 1 ms 6552 KB Output is correct
6 Correct 1 ms 6552 KB Output is correct
7 Correct 0 ms 6552 KB Output is correct
8 Correct 0 ms 6552 KB Output is correct
9 Correct 2 ms 6552 KB Output is correct
10 Correct 0 ms 6552 KB Output is correct

Subtask #3
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 6552 KB Output is correct
2 Correct 79 ms 6552 KB Output is correct
3 Correct 63 ms 6552 KB Output is correct
4 Correct 70 ms 6552 KB Output is correct
5 Correct 68 ms 6552 KB Output is correct
6 Correct 77 ms 6552 KB Output is correct
7 Correct 63 ms 6552 KB Output is correct
8 Correct 44 ms 6552 KB Output is correct
9 Correct 70 ms 6552 KB Output is correct
10 Correct 75 ms 6552 KB Output is correct
11 Correct 26 ms 6552 KB Output is correct
12 Correct 52 ms 6552 KB Output is correct
13 Correct 73 ms 6552 KB Output is correct
14 Correct 57 ms 6552 KB Output is correct
15 Correct 66 ms 6552 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6552 KB Output is correct
2 Correct 72 ms 6552 KB Output is correct
3 Correct 81 ms 6552 KB Output is correct
4 Correct 70 ms 6552 KB Output is correct
5 Correct 64 ms 6552 KB Output is correct
6 Correct 83 ms 6552 KB Output is correct
7 Correct 77 ms 6552 KB Output is correct
8 Correct 65 ms 6552 KB Output is correct
9 Correct 43 ms 6552 KB Output is correct
10 Correct 65 ms 6552 KB Output is correct
11 Correct 57 ms 6552 KB Output is correct
12 Correct 77 ms 6552 KB Output is correct
13 Correct 74 ms 6552 KB Output is correct
14 Correct 63 ms 6552 KB Output is correct
15 Correct 85 ms 6552 KB Output is correct