結果

問題 No.5011 Better Mo's Algorithm is Needed!! (Weighted)
ユーザー tko919tko919
提出日時 2022-12-17 00:12:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 85 ms / 5,000 ms
コード長 5,299 bytes
コンパイル時間 3,218 ms
実行使用メモリ 6,292 KB
スコア 35,492,209,778
最終ジャッジ日時 2022-12-17 00:13:33
合計ジャッジ時間 53,482 ms
ジャッジサーバーID
(参考情報)
judge12 / judge16
純コード判定しない問題か言語
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
6,252 KB
testcase_01 AC 75 ms
6,256 KB
testcase_02 AC 73 ms
6,152 KB
testcase_03 AC 73 ms
6,144 KB
testcase_04 AC 73 ms
6,224 KB
testcase_05 AC 73 ms
6,280 KB
testcase_06 AC 74 ms
6,212 KB
testcase_07 AC 73 ms
6,212 KB
testcase_08 AC 76 ms
6,264 KB
testcase_09 AC 74 ms
6,292 KB
testcase_10 AC 72 ms
6,208 KB
testcase_11 AC 74 ms
6,276 KB
testcase_12 AC 75 ms
6,156 KB
testcase_13 AC 73 ms
6,224 KB
testcase_14 AC 74 ms
6,180 KB
testcase_15 AC 74 ms
6,144 KB
testcase_16 AC 73 ms
6,204 KB
testcase_17 AC 73 ms
6,256 KB
testcase_18 AC 73 ms
6,208 KB
testcase_19 AC 74 ms
6,144 KB
testcase_20 AC 73 ms
6,192 KB
testcase_21 AC 74 ms
6,172 KB
testcase_22 AC 73 ms
6,152 KB
testcase_23 AC 73 ms
6,184 KB
testcase_24 AC 75 ms
6,288 KB
testcase_25 AC 73 ms
6,144 KB
testcase_26 AC 74 ms
6,256 KB
testcase_27 AC 73 ms
6,216 KB
testcase_28 AC 73 ms
6,148 KB
testcase_29 AC 74 ms
6,220 KB
testcase_30 AC 75 ms
6,180 KB
testcase_31 AC 74 ms
6,248 KB
testcase_32 AC 73 ms
6,208 KB
testcase_33 AC 74 ms
6,256 KB
testcase_34 AC 74 ms
6,148 KB
testcase_35 AC 73 ms
6,192 KB
testcase_36 AC 74 ms
6,224 KB
testcase_37 AC 73 ms
6,204 KB
testcase_38 AC 74 ms
6,264 KB
testcase_39 AC 75 ms
6,220 KB
testcase_40 AC 73 ms
6,208 KB
testcase_41 AC 74 ms
6,272 KB
testcase_42 AC 74 ms
6,180 KB
testcase_43 AC 73 ms
6,148 KB
testcase_44 AC 73 ms
6,212 KB
testcase_45 AC 75 ms
6,224 KB
testcase_46 AC 73 ms
6,212 KB
testcase_47 AC 74 ms
6,260 KB
testcase_48 AC 74 ms
6,212 KB
testcase_49 AC 73 ms
6,180 KB
testcase_50 AC 74 ms
6,248 KB
testcase_51 AC 74 ms
6,252 KB
testcase_52 AC 74 ms
6,148 KB
testcase_53 AC 73 ms
6,212 KB
testcase_54 AC 74 ms
6,152 KB
testcase_55 AC 73 ms
6,224 KB
testcase_56 AC 73 ms
6,152 KB
testcase_57 AC 75 ms
6,192 KB
testcase_58 AC 73 ms
6,284 KB
testcase_59 AC 74 ms
6,144 KB
testcase_60 AC 74 ms
6,152 KB
testcase_61 AC 74 ms
6,156 KB
testcase_62 AC 73 ms
6,148 KB
testcase_63 AC 74 ms
6,260 KB
testcase_64 AC 72 ms
6,220 KB
testcase_65 AC 74 ms
6,152 KB
testcase_66 AC 73 ms
6,228 KB
testcase_67 AC 73 ms
6,156 KB
testcase_68 AC 74 ms
6,148 KB
testcase_69 AC 73 ms
6,152 KB
testcase_70 AC 74 ms
6,220 KB
testcase_71 AC 74 ms
6,180 KB
testcase_72 AC 74 ms
6,184 KB
testcase_73 AC 73 ms
6,252 KB
testcase_74 AC 73 ms
6,192 KB
testcase_75 AC 74 ms
6,152 KB
testcase_76 AC 73 ms
6,224 KB
testcase_77 AC 74 ms
6,148 KB
testcase_78 AC 85 ms
6,212 KB
testcase_79 AC 73 ms
6,276 KB
testcase_80 AC 74 ms
6,184 KB
testcase_81 AC 73 ms
6,152 KB
testcase_82 AC 79 ms
6,268 KB
testcase_83 AC 74 ms
6,216 KB
testcase_84 AC 75 ms
6,188 KB
testcase_85 AC 73 ms
6,216 KB
testcase_86 AC 84 ms
6,152 KB
testcase_87 AC 73 ms
6,148 KB
testcase_88 AC 74 ms
6,204 KB
testcase_89 AC 73 ms
6,144 KB
testcase_90 AC 75 ms
6,284 KB
testcase_91 AC 73 ms
6,156 KB
testcase_92 AC 74 ms
6,156 KB
testcase_93 AC 74 ms
6,260 KB
testcase_94 AC 73 ms
6,144 KB
testcase_95 AC 75 ms
6,260 KB
testcase_96 AC 74 ms
6,184 KB
testcase_97 AC 73 ms
6,220 KB
testcase_98 AC 73 ms
6,216 KB
testcase_99 AC 73 ms
6,256 KB
testcase_100 AC 73 ms
6,220 KB
testcase_101 AC 75 ms
6,188 KB
testcase_102 AC 74 ms
6,224 KB
testcase_103 AC 73 ms
6,152 KB
testcase_104 AC 73 ms
6,180 KB
testcase_105 AC 74 ms
6,156 KB
testcase_106 AC 73 ms
6,144 KB
testcase_107 AC 74 ms
6,212 KB
testcase_108 AC 74 ms
6,184 KB
testcase_109 AC 73 ms
6,264 KB
testcase_110 AC 74 ms
6,192 KB
testcase_111 AC 74 ms
6,180 KB
testcase_112 AC 73 ms
6,260 KB
testcase_113 AC 73 ms
6,252 KB
testcase_114 AC 74 ms
6,180 KB
testcase_115 AC 74 ms
6,284 KB
testcase_116 AC 74 ms
6,152 KB
testcase_117 AC 74 ms
6,152 KB
testcase_118 AC 73 ms
6,208 KB
testcase_119 AC 73 ms
6,148 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#line 1 "library/Template/template.hpp"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
using ll=long long int;
const int inf = 0x3fffffff;
const ll INF = 0x1fffffffffffffff;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
#line 2 "library/Utility/fastio.hpp"
#include <unistd.h>

class FastIO{
    static constexpr int L=1<<16;
    char rdbuf[L];
    int rdLeft=0,rdRight=0;
    inline void reload(){
        int len=rdRight-rdLeft;
        memmove(rdbuf,rdbuf+rdLeft,len);
        rdLeft=0,rdRight=len;
        rdRight+=fread(rdbuf+len,1,L-len,stdin);
    }
    inline bool skip(){
        for(;;){
            while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;
            if(rdLeft==rdRight){
                reload();
                if(rdLeft==rdRight)return false;
            }
            else break;
        }
        return true;
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){
            x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));
        }
        return true;
    }
    template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){
        if(!skip())return false;
        if(rdLeft+20>=rdRight)reload();
        bool neg=false;
        if(rdbuf[rdLeft]=='-'){
            neg=true;
            rdLeft++;
        }
        x=0;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x=x*10+(rdbuf[rdLeft++]^48);
        }
        if(rdbuf[rdLeft]!='.')return true;
        rdLeft++;
        T base=.1;
        while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){
            x+=base*(rdbuf[rdLeft++]^48);
            base*=.1;
        }
        if(neg)x=-x;
        return true;
    }
    inline bool _read(char& x){
        if(!skip())return false;
        if(rdLeft+1>=rdRight)reload();
        x=rdbuf[rdLeft++];
        return true;
    }
    inline bool _read(string& x){
        if(!skip())return false;
        for(;;){
            int pos=rdLeft;
            while(pos<rdRight and rdbuf[pos]>' ')pos++;
            x.append(rdbuf+rdLeft,pos-rdLeft);
            if(rdLeft==pos)break;
            rdLeft=pos;
            if(rdLeft==rdRight)reload();
            else break;
        }
        return true;
    }
    template<typename T>inline bool _read(vector<T>& v){
        for(auto& x:v){
            if(!_read(x))return false;
        }
        return true;
    }

    char wtbuf[L],tmp[50];
    int wtRight=0;
    inline void flush(){
        fwrite(wtbuf,1,wtRight,stdout);
        wtRight=0;
    }
    inline void _write(const char& x){
        if(wtRight>L-32)flush();
        wtbuf[wtRight++]=x;
    }
    inline void _write(const string& x){
        for(auto& c:x)_write(c);
    }
    template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){
        if(wtRight>L-32)flush();
        if(x==0){
            _write('0');
            return;
        }
        else if(x<0){
            _write('-');
            if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {
                switch (sizeof(x)) {
                case 2: _write("32768"); return;
                case 4: _write("2147483648"); return;
                case 8: _write("9223372036854775808"); return;
                }
            }
            x=-x;
        }
        int pos=0;
        while(x!=0){
            tmp[pos++]=char((x%10)|48);
            x/=10;
        }
        rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];
        wtRight+=pos;
    }
    template<typename T>inline void _write(const vector<T>& v){
        rep(i,0,v.size()){
            if(i)_write(' ');
            _write(v[i]);
        }
    }
public:
    FastIO(){}
    ~FastIO(){flush();}
    inline void read(){}
    template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){
        assert(_read(head));
        read(tail...); 
    }
    template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}
    template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){
        if(space)_write(' ');
        _write(head);
        write<ln,true>(tail...); 
    }
};

/**
 * @brief Fast IO
 */
#line 3 "sol.cpp"


FastIO io;
int main(){
    int N,Q,WT,ST;
    io.read(N,Q,WT,ST);
    vector<int> w(N);
    io.read(w);
    vector<int> L(Q),R(Q);
    rep(i,0,Q)io.read(L[i],R[i]),L[i]--;
    
    int width = max<int>(1, 1.0 * N / max<double>(1.0, sqrt(Q * 2.0 / 3.0)));
    vector<int> ord(Q);
    iota(ALL(ord),0);
    sort(ALL(ord),[&](int a,int b){
      int ablock = L[a] / width, bblock = L[b] / width;
      if (ablock != bblock) return ablock < bblock;
      if (ablock & 1) return R[a] < R[b];
      return R[a] > R[b];
    });
    rep(i,0,Q)io.write(ord[i]+1);
    return 0;
}
0