結果

問題 No.1471 Sort Queries
ユーザー mugen_1337mugen_1337
提出日時 2021-04-17 15:56:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 161 ms / 2,000 ms
コード長 3,703 bytes
コンパイル時間 3,444 ms
コンパイル使用メモリ 251,316 KB
実行使用メモリ 4,456 KB
最終ジャッジ日時 2023-09-17 01:14:08
合計ジャッジ時間 5,557 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,384 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 35 ms
4,380 KB
testcase_14 AC 29 ms
4,376 KB
testcase_15 AC 42 ms
4,376 KB
testcase_16 AC 12 ms
4,380 KB
testcase_17 AC 28 ms
4,376 KB
testcase_18 AC 23 ms
4,380 KB
testcase_19 AC 15 ms
4,380 KB
testcase_20 AC 45 ms
4,380 KB
testcase_21 AC 28 ms
4,380 KB
testcase_22 AC 25 ms
4,376 KB
testcase_23 AC 88 ms
4,376 KB
testcase_24 AC 89 ms
4,380 KB
testcase_25 AC 121 ms
4,376 KB
testcase_26 AC 69 ms
4,380 KB
testcase_27 AC 123 ms
4,376 KB
testcase_28 AC 118 ms
4,376 KB
testcase_29 AC 70 ms
4,380 KB
testcase_30 AC 83 ms
4,380 KB
testcase_31 AC 103 ms
4,376 KB
testcase_32 AC 86 ms
4,380 KB
testcase_33 AC 81 ms
4,452 KB
testcase_34 AC 161 ms
4,376 KB
testcase_35 AC 161 ms
4,376 KB
testcase_36 AC 18 ms
4,380 KB
testcase_37 AC 19 ms
4,380 KB
testcase_38 AC 83 ms
4,384 KB
testcase_39 AC 77 ms
4,456 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;

template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using set_kth_less=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>
using set_kth_greater=tree<T,null_type,greater<T>,rb_tree_tag,tree_order_statistics_node_update>;

struct Mo{
    using F=function<void(int)>;
    int n,idx,ql,qr;
    vector<pair<int,int>> query;
    vector<int> ord;
    // [l,r) 
    // add_left  : l-1を足す, add_right : rを足す
    // erase_left: lを消す,  erase_right: r-1を消す
    F add_left,add_right,erase_left,erase_right;
 
    Mo(int n,F add_left,F add_right,F erase_left,F erase_right):
    n(n),idx(0),ql(0),qr(0),
    add_left(add_left),add_right(add_right),erase_left(erase_left),erase_right(erase_right)
    {}
 
    void add(int l,int r){
        query.emplace_back(l,r);
    }
 
    void build(){
        int q=(int)query.size();
        int bs=n/min(n,int(sqrt(q)));
        // 左端のブロックでソート
        // 左端のブロックが同じなら右端でソート
        ord.resize(q);
        iota(begin(ord),end(ord),0);
        sort(begin(ord),end(ord),[&](int a,int b){
            int al=query[a].first/bs,bl=query[b].first/bs;
            if(al!=bl) return al<bl;
            // 偶奇で始点を左右に振ると動きに無駄がない
            if(al&1) return query[a].second>query[b].second;
            return query[a].second<query[b].second;
        });
    }
 
    // 1個クエリを進め，処理したクエリのindexを返す
    // processが終わってから結果を格納すること
    // ans[process()]=res;とかはヤバイので注意．実装がよくない
    int process(){
        if(idx>=(int)ord.size()) return -1;
        int now=ord[idx++];
        while(ql>query[now].first)  add_left(--ql);
        while(qr<query[now].second) add_right(qr++);
        while(ql<query[now].first)  erase_left(ql++);
        while(qr>query[now].second) erase_right(--qr);
        return now;
    }
};


signed main(){
    int n,q;cin>>n>>q;
    string s;cin>>s;

    unordered_map<char,int> cnt;
    using P=pair<char,int>;
    set_kth_less<P> st;

    auto add=[&](int i){
        st.insert({s[i],cnt[s[i]]});
        cnt[s[i]]++;
    };
    auto erase=[&](int i){
        cnt[s[i]]--;
        st.erase({s[i],cnt[s[i]]});
    };

    Mo mo(n,add,add,erase,erase);

    vector<int> l(q),r(q),x(q);
    rep(i,q){
        cin>>l[i]>>r[i]>>x[i];
        l[i]--,x[i]--;
        mo.add(l[i],r[i]);
    }

    vector<char> ans(q);

    mo.build();


    rep(i,q){
        int j=mo.process();
        ans[j]=st.find_by_order(x[j])->first;
    }
    rep(i,q) cout<<ans[i]<<endl;
    return 0;
}
0