結果
問題 | No.1471 Sort Queries |
ユーザー |
![]() |
提出日時 | 2023-03-23 07:17:33 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 460 ms / 2,000 ms |
コード長 | 2,743 bytes |
コンパイル時間 | 3,317 ms |
コンパイル使用メモリ | 260,464 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-18 15:17:02 |
合計ジャッジ時間 | 8,220 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#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); } }