結果
| 問題 | No.1471 Sort Queries |
| ユーザー |
 imabc
|
| 提出日時 | 2023-07-20 18:40:30 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,817 bytes |
| コンパイル時間 | 1,876 ms |
| コンパイル使用メモリ | 179,944 KB |
| 実行使用メモリ | 13,888 KB |
| 最終ジャッジ日時 | 2024-09-20 14:46:13 |
| 合計ジャッジ時間 | 8,143 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 1 ms
5,376 KB |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | TLE | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
struct Mo {
int n;
vector< pair< int, int > > lr;
explicit Mo(int n) : n(n) {}
void add(int l, int r) { /* [l, r) */
lr.emplace_back(l, r);
}
template< typename AL, typename AR, typename EL, typename ER, typename O >
void build(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out) {
int q = (int) lr.size();
int bs = n / min< int >(n, sqrt(q));
vector< int > ord(q);
iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), [&](int a, int b) {
int ablock = lr[a].first / bs, bblock = lr[b].first / bs;
if(ablock != bblock) return ablock < bblock;
return (ablock & 1) ? lr[a].second > lr[b].second : lr[a].second < lr[b].second;
});
int l = 0, r = 0;
for(auto idx : ord) {
while(l > lr[idx].first) add_left(--l);
while(r < lr[idx].second) add_right(r++);
while(l < lr[idx].first) erase_left(l++);
while(r > lr[idx].second) erase_right(--r);
out(idx);
}
}
template< typename A, typename E, typename O >
void build(const A &add, const E &erase, const O &out) {
build(add, add, erase, erase, out);
}
};
int main(){
int N,Q; cin>>N>>Q;
string S; cin>>S;
Mo mo(N);
int X[N];
for(int i=0;i<Q;i++){
int l,r; cin>>l>>r;
mo.add(l-1,r);
cin>>X[i];
}
vector<int> cnt(26,0);
vector<char> ans(Q);
auto add = [&](int i) {
cnt[S[i]-'a']++;
};
auto erase = [&](int i) {
cnt[S[i]-'a']--;
};
auto out = [&](int q) {
int sum=0;
for(int i=0;i<26;i++){
sum+=cnt[i];
if(sum>=X[q]){
ans[q]='a'+i;
break;
}
}
};
mo.build(add, erase, out);
for(int i=0;i<Q;i++)cout<<ans[i]<<endl;
}