結果
問題 | No.1471 Sort Queries |
ユーザー | AC2K |
提出日時 | 2023-03-23 07:17:33 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 514 ms / 2,000 ms |
コード長 | 2,743 bytes |
コンパイル時間 | 3,420 ms |
コンパイル使用メモリ | 261,812 KB |
実行使用メモリ | 4,368 KB |
最終ジャッジ日時 | 2023-10-18 19:21:10 |
合計ジャッジ時間 | 10,173 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 2 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,348 KB |
testcase_09 | AC | 2 ms
4,348 KB |
testcase_10 | AC | 2 ms
4,348 KB |
testcase_11 | AC | 2 ms
4,348 KB |
testcase_12 | AC | 2 ms
4,348 KB |
testcase_13 | AC | 43 ms
4,348 KB |
testcase_14 | AC | 35 ms
4,348 KB |
testcase_15 | AC | 48 ms
4,348 KB |
testcase_16 | AC | 12 ms
4,348 KB |
testcase_17 | AC | 36 ms
4,348 KB |
testcase_18 | AC | 30 ms
4,348 KB |
testcase_19 | AC | 14 ms
4,348 KB |
testcase_20 | AC | 50 ms
4,348 KB |
testcase_21 | AC | 32 ms
4,348 KB |
testcase_22 | AC | 31 ms
4,348 KB |
testcase_23 | AC | 123 ms
4,348 KB |
testcase_24 | AC | 123 ms
4,348 KB |
testcase_25 | AC | 168 ms
4,348 KB |
testcase_26 | AC | 86 ms
4,348 KB |
testcase_27 | AC | 187 ms
4,348 KB |
testcase_28 | AC | 183 ms
4,348 KB |
testcase_29 | AC | 88 ms
4,348 KB |
testcase_30 | AC | 117 ms
4,348 KB |
testcase_31 | AC | 147 ms
4,348 KB |
testcase_32 | AC | 115 ms
4,348 KB |
testcase_33 | AC | 514 ms
4,368 KB |
testcase_34 | AC | 249 ms
4,364 KB |
testcase_35 | AC | 247 ms
4,360 KB |
testcase_36 | AC | 462 ms
4,368 KB |
testcase_37 | AC | 473 ms
4,368 KB |
testcase_38 | AC | 362 ms
4,368 KB |
testcase_39 | AC | 446 ms
4,368 KB |
ソースコード
#line 2 "library/template.hpp" #include<bits/stdc++.h> using namespace std; #define rep(i, N) for(int i=0;i<(N);i++) #define all(x) (x).begin(),(x).end() #define popcount(x) __builtin_popcount(x) using i128=__int128_t; using ll = long long; using ld = long double; using graph = vector<vector<int>>; using P = pair<int, int>; constexpr int inf = 1e9; constexpr ll infl = 1e18; constexpr ld eps = 1e-6; const long double pi = acos(-1); constexpr uint64_t MOD = 1e9 + 7; constexpr uint64_t MOD2 = 998244353; constexpr int dx[] = { 1,0,-1,0 }; constexpr int dy[] = { 0,1,0,-1 }; template<class T>inline void chmax(T&x,T y){if(x<y)x=y;} template<class T>inline void chmin(T&x,T y){if(x>y)x=y;} #line 1 "library/other/mo.hpp" class Mo { int n; vector<pair<int, int>> lr; vector<int> ord; public: explicit Mo(int n) : n(n) { lr.reserve(n); } void add(int l, int r) { lr.emplace_back(l, r); } private: inline void line_up() { int q = lr.size(); int bs = n / min<int>(n, (int)sqrt(q)); ord.resize(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; }); } public: 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) { line_up(); int l = 0, r = 0; for (const 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); } }; /// @brief mo's algorithm /// @docs docs/other/mo.md #line 3 "main.cpp" int main(){ int n,q; scanf("%d %d",&n,&q); char str[n]; scanf("%s", str); Mo mo(q); vector<int> x(q); for (auto& xi : x) { int l, r; scanf("%d%d%d", &l, &r, &xi); l--; mo.add(l, r); xi--; } multiset<char> st; auto add = [&](int p) { st.emplace(str[p]); }; auto erase = [&](int p) { st.erase(st.find(str[p])); }; vector<char> ans(q); auto out = [&](int p) { ans[p] = *next(st.begin(), x[p]); }; mo.build(add, erase, out); for (auto& a : ans) { printf("%c\n", a); } }