結果

問題 No.1471 Sort Queries
コンテスト
ユーザー 小野寺健
提出日時 2021-04-25 16:21:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 1,548 bytes
コンパイル時間 762 ms
コンパイル使用メモリ 76,828 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2024-07-04 09:29:49
合計ジャッジ時間 3,012 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

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