結果

問題 No.5012 Better Mo's Algorithm is Needed!! (Execute)
ユーザー 👑 Nachia
提出日時 2022-12-17 00:36:09
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 51 ms / 500 ms
コード長 5,103 bytes
コンパイル時間 1,145 ms
実行使用メモリ 7,920 KB
スコア 1,000,000,000,092,809,462
最終ジャッジ日時 2022-12-17 00:37:37
合計ジャッジ時間 84,177 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge16
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 99
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "Main.cpp"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <atcoder/modint>
#line 2 "nachia\\misc\\sorting.hpp"

#line 4 "nachia\\misc\\sorting.hpp"
#include <cassert>
#line 6 "nachia\\misc\\sorting.hpp"

namespace nachia{

template<class Iterator>
void EnsurePermutation(Iterator first, Iterator last){
    int n = std::distance(first, last);
    std::vector<int> vis(n, 0);
    for(Iterator i=first; i!=last; i++){
        assert(0 <= *i);
        assert(*i < n);
        assert(vis[*i] == 0);
        vis[*i] = 1;
    }
}

template<class T> std::vector<T> Permute(
    const std::vector<T>& src,
    const std::vector<int>& perm
){
    const bool DEBUG = true;
    int n = src.size();
    if constexpr (DEBUG){
        assert(perm.size() == src.size());
        EnsurePermutation(perm.begin(), perm.end());
    }
    std::vector<T> res;
    res.reserve(n);
    for(int i=0; i<n; i++) res.push_back(src[perm[i]]);
    return res;
}

template<class T> std::vector<T>& PermuteInPlace(
    std::vector<T>& src,
    std::vector<int> perm
){
    const bool DEBUG = true;
    int n = src.size();
    if constexpr (DEBUG){
        assert(perm.size() == src.size());
        EnsurePermutation(perm.begin(), perm.end());
    }
    for(int s=0; s<n; s++){
        int p = s;
        while(perm[p] != s){
            std::swap(src[p], src[perm[p]]);
            std::swap(p, perm[p]);
        }
        perm[p] = p;
    }
    return src;
}

// stable sort
std::vector<int> BucketSortPermutation(
    std::vector<int>::const_iterator first,
    std::vector<int>::const_iterator last,
    int maxVal
){
    const bool DEBUG = true;
    int n = last - first;
    if constexpr (DEBUG){
        for(auto itr = first; itr != last; itr++){
            assert(0 <= *itr);
            assert(*itr <= maxVal);
        }
    }
    std::vector<int> cnt(maxVal+2);
    std::vector<int> res(n);
    for(int i=0; i<n; i++) cnt[first[i]+1]++;
    for(int i=0; i<maxVal; i++) cnt[i+1] += cnt[i];
    for(int i=0; i<n; i++) res[cnt[first[i]]++] = i;
    return res;
}

// stable sort
template<class T, class Mapping>
std::vector<int> BucketSortPermutation(
    typename std::vector<T>::const_iterator first,
    typename std::vector<T>::const_iterator last,
    const Mapping& f,
    int maxVal
){
    std::vector<int> buf(last - first);
    auto bufitr = buf.begin();
    for(auto itr = first; itr != last; itr++, bufitr++) *bufitr = f(*itr);
    return BucketSortPermutation(buf.begin(), buf.end(), maxVal);
}

// stable sort
template<class T, class Mapping>
std::vector<T> BucketSort(
    std::vector<T> src,
    const Mapping& f,
    int maxVal
){
    return PermuteInPlace(src, BucketSortPermutation<T>(src.begin(), src.end(), f, maxVal));
}

// stable sort
template<class Iter, class Mapping>
std::vector<int> BucketSortPermutation(
    Iter first,
    Iter last,
    const Mapping& f,
    int maxVal
){
    std::vector<int> buf(std::distance(first, last));
    auto bufitr = buf.begin();
    for(auto itr = first; itr != last; itr++, bufitr++) *bufitr = f(*itr);
    return BucketSortPermutation(buf.begin(), buf.end(), maxVal);
}

template<class Iter> void PermuteInPlace(
    Iter srcFirst,
    Iter srcLast,
    std::vector<int> perm
){
    const bool DEBUG = true;
    int n = std::distance(srcFirst, srcLast);
    if constexpr (DEBUG){
        assert(perm.size() == (size_t)n);
        EnsurePermutation(perm.begin(), perm.end());
    }
    for(int s=0; s<n; s++){
        int p = s;
        while(perm[p] != s){
            std::swap(srcFirst[p], srcFirst[perm[p]]);
            std::swap(p, perm[p]);
        }
        perm[p] = p;
    }
}

// stable sort
template<class Iter, class Mapping>
void BucketSort(
    Iter destFirst,
    Iter destLast,
    const Mapping& f,
    int maxVal
){
    PermuteInPlace(destFirst, destLast, BucketSortPermutation(destFirst, destLast, f, maxVal));
}

}
#line 8 "Main.cpp"

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;


int main(){
    struct Range { int l, r, i; };
    int N, Q; cin >> N >> Q;
    vector<int> A(N); rep(i,N) cin >> A[i];
    vector<Range> G(Q);
    int sqrtN = 1; while(sqrtN * sqrtN <= N) sqrtN++;
    rep(i,Q){ G[i].i = i+1; cin >> G[i].l >> G[i].r; G[i].l--; }
    G = nachia::BucketSort(G, [&](Range g){ return g.r%2 ? g.l%sqrtN : sqrtN-g.l%sqrtN; }, sqrtN);
    G = nachia::BucketSort(G, [&](Range g){ return g.l/sqrtN%2 ? g.r%sqrtN : sqrtN-g.r%sqrtN; }, sqrtN);
    G = nachia::BucketSort(G, [&](Range g){ return g.r/sqrtN%2 ? g.l/sqrtN : sqrtN-g.l/sqrtN; }, sqrtN);
    G = nachia::BucketSort(G, [&](Range g){ return g.r/sqrtN; }, sqrtN);
    rep(i,Q){
        if(i) cout << ' ';
        cout << G[i].i;
    }
    cout << '\n';
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0