#651425 (C++14) No.1471 Sort Queries

• 問題: No.1471 Sort Queries
• ユーザー: 小野寺健
• 提出日時: 2021-04-25 16:19:33
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,548 bytes
• コンパイル時間: 803 ms
• コンパイル使用メモリ: 76,768 KB
• 実行使用メモリ: 10,988 KB
• 最終ジャッジ日時: 2024-07-04 09:29:45
• 合計ジャッジ時間: 2,766 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	5 ms; 9,768 KB
testcase_01	AC	5 ms; 9,756 KB
testcase_02	AC	5 ms; 9,744 KB
testcase_03	AC	5 ms; 9,748 KB
testcase_04	AC	5 ms; 9,796 KB
testcase_05	AC	6 ms; 9,664 KB
testcase_06	AC	5 ms; 9,728 KB
testcase_07	AC	5 ms; 9,732 KB
testcase_08	AC	4 ms; 9,796 KB
testcase_09	AC	5 ms; 9,728 KB
testcase_10	AC	6 ms; 9,736 KB
testcase_11	AC	5 ms; 9,764 KB
testcase_12	AC	4 ms; 9,676 KB
testcase_13	AC	20 ms; 10,220 KB
testcase_14	AC	20 ms; 10,164 KB
testcase_15	AC	30 ms; 10,212 KB
testcase_16	AC	15 ms; 10,000 KB
testcase_17	AC	16 ms; 10,240 KB
testcase_18	AC	13 ms; 10,080 KB
testcase_19	AC	17 ms; 9,860 KB
testcase_20	AC	30 ms; 10,200 KB
testcase_21	AC	18 ms; 10,200 KB
testcase_22	AC	16 ms; 10,176 KB
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-

ソースコード

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

#define MAX_N	100000
#define MAX_M	5000

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();
}