結果

問題 No.5011 Better Mo's Algorithm is Needed!! (Weighted)
ユーザー t33ft33f
提出日時 2022-12-17 02:31:34
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 96 ms / 5,000 ms
コード長 1,069 bytes
コンパイル時間 1,082 ms
実行使用メモリ 8,028 KB
スコア 35,589,556,949
最終ジャッジ日時 2022-12-17 02:32:47
合計ジャッジ時間 51,829 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 120
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdlib>
#include <vector>
#include <algorithm>
#include <array>
#include <numeric>
#include <cstdio>
#include <iostream>
using namespace std;

constexpr int N = 200000, Q = 200000;
int WT, ST;
int W[N], L[Q], R[Q];

int main(int argc, char **argv) {
    scanf("%*d %*d %d %d", &WT, &ST);
    for (int i = 0; i < N; i++) scanf(" %d", W + i);
    for (int i = 0; i < Q; i++) scanf(" %d %d", L + i, R + i);
    array<int, N> a;
    iota(a.begin(), a.end(), 0);
    const int B = argc == 1 ? 550 : atoi(argv[1]);
    vector<vector<int>> buckets((N + B - 1) / B + 1);
    for (int i = 0; i < Q; i++) {
        const int b = L[i] / B;
        buckets[b].push_back(i);
    }
    for (int b = 0; b < buckets.size(); ++b) {
        vector<int> &elems = buckets[b];
        sort(elems.begin(), elems.end(), [b](int i, int j) {
            if (b % 2 == 0) return make_pair(R[i], L[i]) < make_pair(R[j], L[j]);
            else return make_pair(R[i], L[i]) > make_pair(R[j], L[j]);
        });
        for (int i : elems) cout << i + 1 << ' ';
    }
    cout << endl;
}
0