結果

問題 No.738 平らな農地
ユーザー MitI_7MitI_7
提出日時 2019-02-08 21:32:15
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 508 ms / 2,000 ms
コード長 15,684 bytes
コンパイル時間 2,563 ms
コンパイル使用メモリ 200,908 KB
実行使用メモリ 35,604 KB
最終ジャッジ日時 2023-09-11 04:00:17
合計ジャッジ時間 24,978 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 11 ms
4,380 KB
testcase_06 AC 13 ms
4,380 KB
testcase_07 AC 9 ms
4,504 KB
testcase_08 AC 5 ms
4,380 KB
testcase_09 AC 3 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 6 ms
4,376 KB
testcase_12 AC 3 ms
4,380 KB
testcase_13 AC 10 ms
4,380 KB
testcase_14 AC 5 ms
4,376 KB
testcase_15 AC 310 ms
30,688 KB
testcase_16 AC 312 ms
31,088 KB
testcase_17 AC 368 ms
31,024 KB
testcase_18 AC 358 ms
30,472 KB
testcase_19 AC 425 ms
32,820 KB
testcase_20 AC 321 ms
31,192 KB
testcase_21 AC 406 ms
32,948 KB
testcase_22 AC 321 ms
31,228 KB
testcase_23 AC 397 ms
32,052 KB
testcase_24 AC 400 ms
31,428 KB
testcase_25 AC 4 ms
4,376 KB
testcase_26 AC 4 ms
4,380 KB
testcase_27 AC 5 ms
4,376 KB
testcase_28 AC 4 ms
4,376 KB
testcase_29 AC 4 ms
4,380 KB
testcase_30 AC 4 ms
4,380 KB
testcase_31 AC 4 ms
4,380 KB
testcase_32 AC 4 ms
4,380 KB
testcase_33 AC 4 ms
4,380 KB
testcase_34 AC 4 ms
4,376 KB
testcase_35 AC 3 ms
4,380 KB
testcase_36 AC 4 ms
4,376 KB
testcase_37 AC 4 ms
4,380 KB
testcase_38 AC 4 ms
4,380 KB
testcase_39 AC 4 ms
4,376 KB
testcase_40 AC 4 ms
4,380 KB
testcase_41 AC 4 ms
4,376 KB
testcase_42 AC 4 ms
4,380 KB
testcase_43 AC 4 ms
4,376 KB
testcase_44 AC 4 ms
4,380 KB
testcase_45 AC 297 ms
33,908 KB
testcase_46 AC 301 ms
31,208 KB
testcase_47 AC 295 ms
32,796 KB
testcase_48 AC 259 ms
31,916 KB
testcase_49 AC 254 ms
31,644 KB
testcase_50 AC 255 ms
32,680 KB
testcase_51 AC 309 ms
33,220 KB
testcase_52 AC 280 ms
31,576 KB
testcase_53 AC 295 ms
32,104 KB
testcase_54 AC 309 ms
33,344 KB
testcase_55 AC 318 ms
33,192 KB
testcase_56 AC 313 ms
32,536 KB
testcase_57 AC 282 ms
31,132 KB
testcase_58 AC 286 ms
32,376 KB
testcase_59 AC 282 ms
33,884 KB
testcase_60 AC 281 ms
33,700 KB
testcase_61 AC 285 ms
33,556 KB
testcase_62 AC 278 ms
31,464 KB
testcase_63 AC 329 ms
33,900 KB
testcase_64 AC 307 ms
33,460 KB
testcase_65 AC 416 ms
31,172 KB
testcase_66 AC 432 ms
32,392 KB
testcase_67 AC 319 ms
32,872 KB
testcase_68 AC 312 ms
33,948 KB
testcase_69 AC 461 ms
34,292 KB
testcase_70 AC 383 ms
35,604 KB
testcase_71 AC 21 ms
8,392 KB
testcase_72 AC 222 ms
29,404 KB
testcase_73 AC 197 ms
27,632 KB
testcase_74 AC 283 ms
30,644 KB
testcase_75 AC 431 ms
32,720 KB
testcase_76 AC 361 ms
33,880 KB
testcase_77 AC 460 ms
32,652 KB
testcase_78 AC 508 ms
35,460 KB
testcase_79 AC 483 ms
35,528 KB
testcase_80 AC 365 ms
34,376 KB
testcase_81 AC 421 ms
33,276 KB
testcase_82 AC 435 ms
34,500 KB
testcase_83 AC 282 ms
31,808 KB
testcase_84 AC 229 ms
30,920 KB
testcase_85 AC 488 ms
35,288 KB
testcase_86 AC 442 ms
32,820 KB
testcase_87 AC 152 ms
34,408 KB
testcase_88 AC 141 ms
32,736 KB
testcase_89 AC 1 ms
4,380 KB
testcase_90 AC 1 ms
4,380 KB
testcase_91 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT_ON(bit, i) (bit & (1LL << i))
#define BIT_COUNT(bit) (__builtin_popcount(bit))

typedef long long LL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<typename T> using VVVV = std::vector<std::vector<std::vector<std::vector<T>>>>;

template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline void print_vec(const std::vector<T> &v) { for (int i = 0; i < v.size(); ++i) {  if (i != 0) {std::cout << " ";} std::cout << v[i];} std::cout << "\n"; }
template<class T> inline void print_2vec(const std::vector<std::vector<T>> &v) { for (int i = 0; i < v.size(); ++i) { for (int j = 0; j < v[0].size(); ++j) { if (j != 0) { std::cout << " "; } std::cout << std::setw(13) << std::left << v[i][j]; } std::cout << "\n";}}
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }
template<class T> inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
template<class T> inline double manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); }
template<typename T> T &chmin(T &a, const T &b) { if (b < a) { a = b; } return a; }
template<typename T> T &chmax(T &a, const T &b) { if (b > a) { a = b; } return a; }
template<class T> inline std::vector<T> unique(std::vector<T> v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); return v; }
// 初項s, 交差dのn個の数列の和
long long sum_of_arithmetic_progression(long long s, long long d, long long n) { return n * (2 * s + (n - 1) * d) / 2; }

const int INF = 1 << 30;
const double EPS = 1e-9;
const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy4 = {0, -1, 0, 1}, dx4 = {1, 0, -1, 0};
const std::vector<int> dy8 = { 0, -1, 0, 1, 1, -1, -1, 1 }, dx8 = { 1, 0, -1, 0, 1, 1, -1, -1 };

using namespace std;

enum {
    NOTFOUND = 0xFFFFFFFFFFFFFFFFLLU
};


class SuccinctBitVector {
public:
    vector<uint32_t> bit;
    vector<int> acc;
    int N;
    SuccinctBitVector(vector<int> bit_) {
        N = bit_.size();
        int N2 = (N >> 5) + 1;
        bit.resize(N2);
        for(int i = 0; i < N2; i++) {
            for(int j = 0; j < 32; j++) {
                if ((i << 5) + j < N) bit[i] |= bit_[(i << 5) + j] << j;
            }
        }
        acc = vector<int>(N2);
        for(int i = 0; i < N2 - 1; i++) {
            acc[i + 1] = acc[i] + __builtin_popcount(bit[i]);
        }
    }
    int rank(int x, int k) {
        int n1 = acc[k >> 5] + __builtin_popcount(bit[k >> 5] & (uint32_t)(((1ULL << (k & 0x1f)) - 1)));
        return x ? n1 : k - n1;
    }

    int operator[](int k) {
        return ((bit[k >> 5] >> (k & 0x1f)) & 1);
    }

    size_t size() {
        return N;
    }
};

class WaveletMatrix {
private:
    std::vector<SuccinctBitVector> bit_arrays;
    std::vector<uint64_t> begin_one;                    // 各bitに着目したときの1の開始位置
    std::map<uint64_t, uint64_t> begin_alphabet;        // 最後のソートされた配列で各文字の開始位置
    std::vector<std::vector<uint64_t>> cumulative_sum;  // 各bitに着目したときの累積和

    uint64_t size;                                 // 与えられた配列のサイズ
    uint64_t maximum_element;                      // 文字数
    uint64_t bit_size;                             // 文字を表すのに必要なbit数

public:
    WaveletMatrix (const std::vector<uint64_t> &array) {
        assert(array.size() > 0);
        size = array.size();
        maximum_element =  *max_element(array.begin(), array.end()) + 1;
        bit_size = get_num_of_bit(maximum_element);
        if (bit_size == 0) {
            bit_size = 1;
        }

//        bit_arrays.resize(bit_size);
//        for (uint64_t i = 0; i < bit_size; ++i) {
//            SuccinctBitVector sv(size);
//            bit_arrays.push_back(sv);
//        }
        this->begin_one.resize(bit_size);
        this->cumulative_sum.resize(bit_size + 1, std::vector<uint64_t>(size + 1, 0));

        for (uint64_t j = 0; j < array.size(); ++j) {
            this->cumulative_sum[0][j + 1] = this->cumulative_sum[0][j] + array[j];
        }

        std::vector<uint64_t> v(array);
        for (uint64_t i = 0; i < bit_size; ++i) {

            std::vector<uint64_t> temp;
            vector<int> b(v.size(), 0);
            // 0をtempにいれてく
            for (uint64_t j = 0; j < v.size(); ++j) {
                uint64_t c = v[j];
                uint64_t bit = (c >> (bit_size - i - 1)) & 1;  //　上からi番目のbit
                if (bit == 0) {
                    temp.push_back(c);
//                    bit_arrays[i].setBit(0, j);
                        b[j] = 0;
                }
            }

            this->begin_one[i] = temp.size();

            // 1をtempにいれてく
            for (uint64_t j = 0; j < v.size(); ++j) {
                uint64_t c = v[j];
                uint64_t bit = (c >> (bit_size - i - 1)) & 1;  //　上からi番目のbit
                if (bit == 1) {
                    temp.push_back(c);
//                    bit_arrays[i].setBit(1, j);
                    b[j] = 1;
                }
            }

            for (uint64_t j = 0; j < temp.size(); ++j) {
                this->cumulative_sum[i + 1][j + 1] = this->cumulative_sum[i + 1][j] + temp[j];
            }

//            bit_arrays[i].build();
assert(b.size() > 0);
            SuccinctBitVector bv(b);
            bit_arrays.emplace_back(bv);
            v = temp;
        }

        // ソートされた配列内での各文字の位置を取得
        for (int i = v.size() - 1; i >= 0; --i) {
            this->begin_alphabet[v[i]] = i;
        }
    }

    // v[begin_pos, end_pos)でk番目に小さい数値のindexを返す(kは0-origin)
    // つまり小さい順に並べてk番目の値
    uint64_t quantileRange(uint64_t begin_pos, uint64_t end_pos, uint64_t k) {
        if ((end_pos > size || begin_pos >= end_pos) || (k >= end_pos - begin_pos)) {
            return NOTFOUND;
        }

        uint64_t val = 0;
        for (uint64_t i = 0; i < bit_size; ++i) {
            const uint64_t num_of_zero_begin = bit_arrays[i].rank(0, begin_pos);
            const uint64_t num_of_zero_end = bit_arrays[i].rank(0, end_pos);
            const uint64_t num_of_zero = num_of_zero_end - num_of_zero_begin;     // beginからendまでにある0の数
            const uint64_t bit = (k < num_of_zero) ? 0 : 1;                       // k番目の値の上からi番目のbitが0か1か

            if (bit) {
                k -= num_of_zero;
                begin_pos = this->begin_one[i] + begin_pos - num_of_zero_begin;
                end_pos = this->begin_one[i] + end_pos - num_of_zero_end;
            }
            else {
                begin_pos = num_of_zero_begin;
                end_pos = num_of_zero_begin + num_of_zero;
            }

            val = ((val << 1) | bit);
        }

        return val;

//        uint64_t left = 0;
//        for (uint64_t i = 0; i < bit_size; ++i) {
//            const uint64_t bit = (val >> (bit_size - i - 1)) & 1;  // 上からi番目のbit
//            left = bit_arrays[i).rank(bit, left);               // cのi番目のbitと同じ数値の数
//            if (bit) {
//                left += this->begin_one[i);
//            }
//        }
//
//        const uint64_t rank = begin_pos + k - left + 1;
//        return select(val, rank) - 1;
    }

    // v[0, pos)のcの数
    uint64_t rank(uint64_t c, uint64_t pos) {
        assert(pos < size);
        if (c >= maximum_element) {
            return 0;
        }
        if (this->begin_alphabet.find(c) == this->begin_alphabet.end()) {
            return 0;
        }

        for (uint64_t i = 0; i < bit_size; ++i) {
            uint64_t bit = (c >> (bit_size - i - 1)) & 1;  // 上からi番目のbit
            pos = bit_arrays[i].rank(bit, pos);         // cのi番目のbitと同じ数値の数
            if (bit) {
                pos += this->begin_one[i];
            }
        }

        uint64_t begin_pos = this->begin_alphabet[c];
        return pos - begin_pos;
    }
//
//    // v[begin_pos, end_pos)で[min, max)に入る値の個数
//    uint64_t rangeFreq(uint64_t begin_pos, uint64_t end_pos, uint64_t min_c, uint64_t max_c) {
//        if ((end_pos > size || begin_pos >= end_pos) || (min_c >= max_c) || min_c >= maximum_element) {
//            return 0;
//        }
//
//        const auto maxi_t = rankAll(max_c, begin_pos, end_pos);
//        const auto mini_t = rankAll(min_c, begin_pos, end_pos);
//        return std::get<1>(maxi_t) - std::get<1>(mini_t);
//    }
//
//    // v[0, pos)でcより小さい文字の数
//    uint64_t rankLessThan(uint64_t c, uint64_t begin, uint64_t end) {
//        auto t = rankAll(c, begin, end);
//        return std::get<1>(t);
//    }
//
//    // v[0, pos)でcより大きい文字の数
//    uint64_t rankMoreThan(uint64_t c, uint64_t begin, uint64_t end) {
//        auto t = rankAll(c, begin, end);
//        return std::get<2>(t);
//    }

    // v[begin, end)で(cと同じ値の数、cより小さい値の数、cより大きい値の数)を求める
    std::tuple<uint64_t, uint64_t, uint64_t> rankAll(const uint64_t c, uint64_t begin, uint64_t end) {
        assert(end <= size);
        const uint64_t num = end - begin;

        if (begin >= end) {
            return std::make_tuple(0, 0, 0);
        }
        if (c >= maximum_element || end == 0) {
            return std::make_tuple(0, num, 0);
        }

        uint64_t rank_less_than = 0, rank_more_than = 0;
        for (size_t i = 0; i < bit_size && begin < end; ++i) {
            const uint64_t bit = (c >> (bit_size - i - 1)) & 1;

            const uint64_t rank0_begin = this->bit_arrays[i].rank(0, begin);
            const uint64_t rank0_end = this->bit_arrays[i].rank(0, end);
            const uint64_t rank1_begin = begin - rank0_begin;
            const uint64_t rank1_end = end - rank0_end;

            if (bit) {
                rank_less_than += (rank0_end - rank0_begin);    // i番目のbitが0のものは除外される
                begin = this->begin_one[i] + rank1_begin;
                end = this->begin_one[i] + rank1_end;
            } else {
                rank_more_than += (rank1_end - rank1_begin);    // i番目のbitが1のものは除外される
                begin = rank0_begin;
                end = rank0_end;
            }
        }

        const uint64_t rank = num - rank_less_than - rank_more_than;
        return std::make_tuple(rank, rank_less_than, rank_more_than);
    }

    // T[begin_pos, end_pos)でx <= c < yを満たすcの和を返す
    uint64_t rangeSum(const uint64_t begin, const uint64_t end, const uint64_t x, const uint64_t y) {
        return rangeSum(begin, end, 0, 0, x, y);
    }

    uint64_t freq(uint64_t l, uint64_t r, uint64_t a, uint64_t b) {
        return freq_dfs(0, l, r, 0, a, b);
    }

    // number of elements in [l,r) in [a,b)
    // O(log m)
    int freq_dfs(uint64_t d, uint64_t l, uint64_t r, uint64_t val, uint64_t a, uint64_t b) {
        if(l == r) return 0;
        if(d == bit_size) return (a <= val and val < b)? r-l: 0;
        uint64_t nv = 1ULL<<(bit_size-d-1)|val, nnv = ((1ULL<<(bit_size-d-1))-1)|nv;
        if(nnv < a or b <= val) return 0;
        if(a <= val and nnv < b) return r-l;
        uint64_t lc = this->bit_arrays[d].rank(1,l);
        uint64_t rc = this->bit_arrays[d].rank(1,r);
        return freq_dfs(d+1,l-lc,r-rc,val,a,b)+
               freq_dfs(d+1,lc+this->begin_one[d],rc+this->begin_one[d],nv,a,b);
    }

    uint64_t kth_number(uint64_t l, uint64_t r, uint64_t k) {
        if(r-l <= k or k < 0) return -1;
        uint64_t ret = 0;
        for (int d = 0; d < bit_size; d++) {
            uint64_t lc = bit_arrays[d].rank(1,l);
            uint64_t rc = bit_arrays[d].rank(1,r);
            // lc - rc = [l, r)で立っている1の数
            if(rc-lc > k) { // 1の数にkが収まっていれば
                l = lc+begin_one[d], r = rc+begin_one[d]; // 1側に遷移
                ret |= 1ULL<<(bit_size-d-1);
            } else { // 0側ならば
                k -= rc-lc; // 1側にあった数だけkを削って次へ
                l -= lc, r -= rc;
            }
        }
        return ret;
    }


private:
    uint64_t get_num_of_bit(uint64_t x) {
        if (x == 0) return 0;
        x--;
        uint64_t bit_num = 0;
        while (x >> bit_num) {
            ++bit_num;
        }
        return bit_num;
    }

    uint64_t rangeSum(const uint64_t begin, const uint64_t end, const uint64_t depth, const uint64_t c, const uint64_t x, const uint64_t y) {
        if (begin == end) {
            return 0;
        }

        if (depth == bit_size) {
            if (x <= c and c < y) {
                return c * (end - begin);   // 値 * 頻度
            }
            return 0;
        }

        const uint64_t next_c = ((uint64_t)1 << (bit_size - depth - 1)) | c;                   // 上からdepth番目のbitを立てる
        const uint64_t all_one_c = (((uint64_t)1 << (bit_size - depth - 1)) - 1) | next_c;     // depth以降のbitをたてる(これ以降全部1を選んだときの値)
        if(all_one_c < x or y <= c) {
            return 0;
        }

        // [begin, pos)のすべての要素は[x, y)
        if (x <= c and all_one_c < y) {
            return this->cumulative_sum[depth][end] - this->cumulative_sum[depth][begin];
        }

        const uint64_t rank0_begin = this->bit_arrays[depth].rank(0, begin);
        const uint64_t rank0_end = this->bit_arrays[depth].rank(0, end);
        const uint64_t rank1_begin = begin - rank0_begin;
        const uint64_t rank1_end = end - rank0_end;

        return rangeSum(rank0_begin, rank0_end, depth + 1, c, x, y) +
               rangeSum(this->begin_one[depth] + rank1_begin, this->begin_one[depth] + rank1_end, depth + 1, next_c, x, y);
    }
};

uint64_t solve(int N, int K, V<uint64_t> &A) {
    WaveletMatrix wm(A);

    uint64_t ans = LONG_LONG_MAX;
    FOR(i, 0, N - K + 1) {
        uint64_t begin = i;
        uint64_t end = i + K;
//        uint64_t m = wm.quantileRange(begin, end, K / 2);
        uint64_t m = wm.kth_number(begin, end, K / 2);

        auto less_sum = wm.rangeSum(begin, end, 0, m);
        auto more_sum = wm.rangeSum(begin, end, m, 1000000010);



        auto less_freq = wm.freq(begin, end, 0, m);
        auto more_freq = wm.freq(begin, end, m, 1000000010);


        auto a = m * less_freq - less_sum;
        auto b = more_sum - m * more_freq;

        chmin(ans, a + b);
    }

    return ans;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, K;
    cin >> N >> K;

    V<uint64_t> A(N);
    FOR(i, 0, N) {
        cin >> A[i];
    }

    print(solve(N, K, A));
}
0