#649371 (C++17) No.1471 Sort Queries

提出ソース

結果

問題	No.1471 Sort Queries
ユーザー	cn_449
提出日時	2021-04-17 23:50:59
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	37 ms / 2,000 ms
コード長	3,846 bytes
コンパイル時間	1,669 ms
コンパイル使用メモリ	143,820 KB
実行使用メモリ	10,240 KB
最終ジャッジ日時	2024-07-04 04:20:54
合計ジャッジ時間	3,253 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	12 ms 6,944 KB
testcase_14	AC	10 ms 6,940 KB
testcase_15	AC	15 ms 6,940 KB
testcase_16	AC	8 ms 6,940 KB
testcase_17	AC	10 ms 6,940 KB
testcase_18	AC	7 ms 6,940 KB
testcase_19	AC	8 ms 6,944 KB
testcase_20	AC	15 ms 6,940 KB
testcase_21	AC	9 ms 6,944 KB
testcase_22	AC	8 ms 6,940 KB
testcase_23	AC	18 ms 7,552 KB
testcase_24	AC	18 ms 7,552 KB
testcase_25	AC	29 ms 9,856 KB
testcase_26	AC	20 ms 6,944 KB
testcase_27	AC	26 ms 10,112 KB
testcase_28	AC	26 ms 10,112 KB
testcase_29	AC	19 ms 6,948 KB
testcase_30	AC	19 ms 7,296 KB
testcase_31	AC	26 ms 7,296 KB
testcase_32	AC	26 ms 6,944 KB
testcase_33	AC	37 ms 10,112 KB
testcase_34	AC	35 ms 10,240 KB
testcase_35	AC	35 ms 10,112 KB
testcase_36	AC	24 ms 10,240 KB
testcase_37	AC	24 ms 10,240 KB
testcase_38	AC	37 ms 10,112 KB
testcase_39	AC	37 ms 10,112 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define range(i, a, b) for (ll i = (a); i < (b); i++)
#define pb push_back
#define debug(x) cerr << __LINE__ << ' ' << #x << ':' << (x) << '\n'
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
template<class T> using pri_s = priority_queue<T, vector<T>, greater<T>>;
template<class T> using pri_b = priority_queue<T>;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr int mod1e9 = 1000000007;
constexpr int mod998 = 998244353;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
constexpr ll ten(int n) { return n ? 10 * ten(n - 1) : 1; };
int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,1,-1 };
ll mul(ll a, ll b) { return (a > INF / b ? INF : a * b); }
void fail() { cout << "-1\n"; exit(0); } void no() { cout << "No\n"; exit(0); }
template<class T> void er(T a) { cout << a << '\n'; exit(0); }
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }
template<class T> istream &operator >> (istream &s, vector<T> &v) { for (auto &e : v) s >> e; return s; }
template<class T> ostream &operator << (ostream &s, const vector<T> &v) { for (auto &e : v) s << e << ' '; return s; }
template<class T, class U> ostream &operator << (ostream &s, const pair<T, U> &p) { s << p.first << ' ' << p.second; return s; }

struct fastio {
	fastio() {
		cin.tie(0); cout.tie(0);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(20);
		cerr << fixed << setprecision(20);
	}
}fastio_;

vector<int> operator + (vector<int> a, vector<int> b) {
	vector<int> res(26);
	rep(i, 26) res[i] = a[i] + b[i];
	return res;
}

template<class T> class segtree {
	int n;
	vector<T> data;
	T id = vector<int>(26);
	T operation(T a, T b) { return a + b; };
public:
	segtree(int _n) {
		n = 1;
		while (n < _n + 2) n <<= 1;
		data = vector<T>(2 * n, id);
	}
	segtree(vector<T> vec) {
		int _n = vec.size();
		n = 1;
		while (n < _n + 2) n <<= 1;
		data = vector<T>(2 * n, id);
		for (int i = 0; i < _n; i++) data[i + n] = vec[i];
		for (int i = n - 1; i >= 1; i--) data[i] = operation(data[i << 1], data[i << 1 | 1]);
	}
	void change(int i, T x) {
		i += n;
		data[i] = x;
		while (i > 1) {
			i >>= 1;
			data[i] = operation(data[i << 1], data[i << 1 | 1]);
		}
	}
	void add(int i, T x) { change(i, data[i + n] + x); }
	T get(int a, int b) {
		T left = id; T right = id;
		a += n; b += n;
		while (a < b) {
			if (a & 1) left = operation(left, data[a++]);
			if (b & 1) right = operation(data[--b], right);
			a >>= 1; b >>= 1;
		}
		return operation(left, right);
	}
	T get_all() { return data[1]; }
	T operator[](int i) { return data[i + n]; }
};

int main() {
	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	vector<vector<int>> v(n, vector<int>(26));
	rep(i, n) v[i][s[i] - 'a']++;
	segtree<vector<int>> seg(v);
	while (q--) {
		int l, r, k;
		cin >> l >> r >> k;
		l--;
		vector<int> res = seg.get(l, r);
		rep(i, 26) {
			if (res[i] < k) {
				k -= res[i];
			}
			else {
				cout << (char)('a' + i) << '\n';
				break;
			}
		}
	}
}

yukicoder

結果

テストケース

ソースコード