結果

問題 No.1471 Sort Queries
ユーザー 小野寺健小野寺健
提出日時 2021-04-25 16:21:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 1,548 bytes
コンパイル時間 711 ms
コンパイル使用メモリ 76,316 KB
実行使用メモリ 11,012 KB
最終ジャッジ日時 2023-09-17 14:07:57
合計ジャッジ時間 3,260 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
9,812 KB
testcase_01 AC 5 ms
9,688 KB
testcase_02 AC 5 ms
9,692 KB
testcase_03 AC 5 ms
9,596 KB
testcase_04 AC 5 ms
9,624 KB
testcase_05 AC 5 ms
9,556 KB
testcase_06 AC 5 ms
9,576 KB
testcase_07 AC 5 ms
9,568 KB
testcase_08 AC 5 ms
9,676 KB
testcase_09 AC 5 ms
9,548 KB
testcase_10 AC 5 ms
9,600 KB
testcase_11 AC 5 ms
9,572 KB
testcase_12 AC 4 ms
9,732 KB
testcase_13 AC 20 ms
10,168 KB
testcase_14 AC 19 ms
10,112 KB
testcase_15 AC 28 ms
10,164 KB
testcase_16 AC 16 ms
9,684 KB
testcase_17 AC 16 ms
10,180 KB
testcase_18 AC 12 ms
9,948 KB
testcase_19 AC 16 ms
9,800 KB
testcase_20 AC 29 ms
10,160 KB
testcase_21 AC 17 ms
10,164 KB
testcase_22 AC 15 ms
10,228 KB
testcase_23 AC 41 ms
10,688 KB
testcase_24 AC 40 ms
10,712 KB
testcase_25 AC 60 ms
10,624 KB
testcase_26 AC 43 ms
10,224 KB
testcase_27 AC 50 ms
10,724 KB
testcase_28 AC 50 ms
10,624 KB
testcase_29 AC 41 ms
10,340 KB
testcase_30 AC 40 ms
10,416 KB
testcase_31 AC 61 ms
10,728 KB
testcase_32 AC 62 ms
10,284 KB
testcase_33 AC 89 ms
10,720 KB
testcase_34 AC 76 ms
10,700 KB
testcase_35 AC 75 ms
10,776 KB
testcase_36 AC 18 ms
10,964 KB
testcase_37 AC 18 ms
10,728 KB
testcase_38 AC 59 ms
10,836 KB
testcase_39 AC 72 ms
11,012 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

#define MAX_N	10000
#define MAX_M	10000

const int ST_SIZE = (1 << 18) - 1;

int N, M;
char A[MAX_N];
int I[MAX_M], J[MAX_M], K[MAX_M];

char nums[MAX_N];
vector<int> dat[ST_SIZE];

void init(int k, int l, int r) {
	if (r - l == 1) {
		dat[k].push_back(A[l]);
	}
	else {
		int lch = k * 2 + 1, rch = k * 2 + 2;
		init(lch, l, (l + r) / 2);
		init(rch, (l + r) / 2, r);
		dat[k].resize(r - l);
		merge(dat[lch].begin(), dat[lch].end(), dat[rch].begin(), dat[rch].end(), dat[k].begin());
	}
}

int query(int i, int j, char x, int k, int l, int r) {
//	printf("query(%d, %d, %d, %d, %d, %d)\n", i, j, x, k, l, r);
	if (j <= l || r <= i) {
		return 0;
	}
	else if (i <= l && r <= j) {
		return upper_bound(dat[k].begin(), dat[k].end(), x) - dat[k].begin();
	}
	else {
		int lc = query(i, j, x, k * 2 + 1, l, (l + r) / 2);
		int rc = query(i, j, x, k * 2 + 2, (l + r) / 2, r);
		return lc + rc;
	}
}

void solve() {
	for (int i=0; i < N; i++) nums[i] = A[i];
	sort(nums, nums + N);

	init(0, 0, N);

	for (int i = 0; i < M; i++) {
		int l = I[i] - 1, r = J[i], k = K[i];

		int lb = -1, ub = N - 1;
		while (ub - lb > 1) {
			int md = (ub + lb) / 2;
			int c = query(l, r, nums[md], 0, 0, N);
			if (c >= k) ub = md;
			else lb = md;
		}
		printf("%c\n", nums[ub]);
	}
}

int main() {
	cin >> N >> M;
	string str;
	cin >> str;
	for (int i = 0; i < N; i++) {
		A[i] = str[i];
	}
	for (int i = 0; i < M; i++) {
		cin >> I[i] >> J[i] >> K[i];
	}
	solve();
}
0