結果

問題 No.1471 Sort Queries
ユーザー 👑 NachiaNachia
提出日時 2021-04-10 09:26:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 63 ms / 2,000 ms
コード長 2,466 bytes
コンパイル時間 1,093 ms
コンパイル使用メモリ 91,596 KB
実行使用メモリ 8,100 KB
最終ジャッジ日時 2024-06-25 22:35:51
合計ジャッジ時間 3,101 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 17 ms
6,940 KB
testcase_14 AC 15 ms
6,940 KB
testcase_15 AC 25 ms
6,940 KB
testcase_16 AC 13 ms
6,940 KB
testcase_17 AC 13 ms
6,940 KB
testcase_18 AC 10 ms
6,944 KB
testcase_19 AC 14 ms
6,940 KB
testcase_20 AC 25 ms
6,940 KB
testcase_21 AC 14 ms
6,944 KB
testcase_22 AC 12 ms
6,944 KB
testcase_23 AC 32 ms
6,944 KB
testcase_24 AC 31 ms
6,940 KB
testcase_25 AC 48 ms
8,100 KB
testcase_26 AC 35 ms
6,944 KB
testcase_27 AC 40 ms
7,864 KB
testcase_28 AC 42 ms
6,944 KB
testcase_29 AC 35 ms
6,940 KB
testcase_30 AC 32 ms
6,944 KB
testcase_31 AC 48 ms
6,940 KB
testcase_32 AC 52 ms
6,944 KB
testcase_33 AC 62 ms
6,940 KB
testcase_34 AC 63 ms
6,948 KB
testcase_35 AC 61 ms
6,940 KB
testcase_36 AC 43 ms
7,864 KB
testcase_37 AC 44 ms
6,944 KB
testcase_38 AC 60 ms
6,944 KB
testcase_39 AC 60 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<
  class S,
  S(*op)(S a,S b),
  S(*e)()
>
struct PersistentSegtree{
  struct Node{ int l,r; S v; };
  int N, logN;
  vector<Node> V;
  void merge(int p){ V[p].v=op(V[V[p].l].v,V[V[p].r].v); }
  PersistentSegtree(int z=0){
    N=1; logN=0; while(N<z){ N*=2; logN++; }
    V.assign(N*2-1,{-1,-1,e()});
    for(int i=N-2; i>=0; i--){ V[i].l=i*2+1; V[i].r=i*2+2; }
  }
  PersistentSegtree(const vector<S>& v)
    : PersistentSegtree(v.size()){
    for(int i; i<v.size(); i++) V[N-1+i].v=v[i];
    for(int i=N-2; i>=0; i--) merge(i);
  }
  int copy_node(int p){ V.push_back(V[p]); return V.size()-1;}
  int set(int t,int p,S v){
    vector<int> P;
    P.push_back(copy_node((t==-1)?0:t));
    for(int d=logN-1; d>=0; d--){
      int pp=P.back();
      if(p&(1<<d)){ P.push_back(copy_node(V[pp].r)); V[pp].r=P.back(); }
      else{ P.push_back(copy_node(V[pp].l)); V[pp].l=P.back(); }
      pp=P.back();
    }
    V[P.back()].v=v;
    for(int i=P.size()-2; i>=0; i--) merge(P[i]);
    return P.front();
  }
  int where(int t,int p){
    int s=(t==-1)?0:t;
    for(int d=logN-1; d>=0; d--) s=((p&(1<<d))?V[s].r:V[s].l);
    return s;
  }
  S get(int t,int p){
    int s=(t==-1)?0:t;
    for(int d=logN-1; d>=0; d--) s=((p&(1<<d))?V[s].r:V[s].l);
    return V[s].v;
  }
  S prod(int t,int l,int r){
    struct DFSV{ int l,r,i; };
    vector<DFSV> G; G.reserve(logN*2+2);
    int s=(t==-1)?0:t;
    G.push_back({0,N,s});
    S res=e();
    while(G.size()){
      DFSV g=G.back(); G.pop_back();
      int a=g.l, b=g.r, i=g.i;
      if(r<=a || b<=l) continue;
      if(l<=a && b<=r){ res=op(res,V[i].v); continue; }
      G.push_back({a,(a+b)/2,V[i].l});
      G.push_back({(a+b)/2,b,V[i].r});
    }
    return res;
  }
};

using RQS = int;
RQS RQe(){ return 0; }
RQS RQop(RQS l,RQS r){ return l+r; }
using RQ = PersistentSegtree<RQS,RQop,RQe>;

int N, Q;
string S;

vector<pair<int,int>> A;
RQ G;
vector<int> RQT;

int main() {
  cin>>N>>Q>>S;
  for(int i=0; i<N; i++) A.push_back({S[i],i});
  sort(A.begin(),A.end());
  G = RQ(N);
  RQT.push_back(-1);
  for(int i=0; i<N; i++) RQT.push_back(G.set(RQT.back(),A[i].second,1));
  for(int i=0; i<Q; i++){
    int l,r,x; cin>>l>>r>>x; l--;
    int lt=-1, rt=N+1;
    while(rt-lt>1){
      int mt=(lt+rt)/2;
      if(G.prod(RQT[mt],l,r)<x) lt=mt; else rt=mt;
    }
    cout<<(char)(A[rt-1].first)<<"\n";
  }
  return 0;
}
0