#288034 (C++11) No.738 平らな農地

提出ソース

結果

問題	No.738 平らな農地
ユーザー	kakira9618
提出日時	2018-09-28 22:30:43
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	233 ms / 2,000 ms
コード長	8,966 bytes
コンパイル時間	1,825 ms
コンパイル使用メモリ	183,132 KB
実行使用メモリ	10,148 KB
最終ジャッジ日時	2024-10-12 06:52:46
合計ジャッジ時間	10,709 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	1 ms 6,820 KB
testcase_05	AC	5 ms 6,816 KB
testcase_06	AC	5 ms 6,816 KB
testcase_07	AC	4 ms 6,820 KB
testcase_08	AC	4 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	3 ms 6,816 KB
testcase_12	AC	3 ms 6,816 KB
testcase_13	AC	4 ms 6,816 KB
testcase_14	AC	3 ms 6,816 KB
testcase_15	AC	98 ms 7,612 KB
testcase_16	AC	102 ms 7,772 KB
testcase_17	AC	113 ms 7,640 KB
testcase_18	AC	107 ms 7,712 KB
testcase_19	AC	135 ms 7,928 KB
testcase_20	AC	104 ms 7,784 KB
testcase_21	AC	128 ms 7,936 KB
testcase_22	AC	104 ms 7,796 KB
testcase_23	AC	121 ms 7,852 KB
testcase_24	AC	124 ms 7,808 KB
testcase_25	AC	2 ms 6,816 KB
testcase_26	AC	2 ms 6,816 KB
testcase_27	AC	3 ms 6,816 KB
testcase_28	AC	3 ms 6,816 KB
testcase_29	AC	3 ms 6,820 KB
testcase_30	AC	3 ms 6,816 KB
testcase_31	AC	2 ms 6,816 KB
testcase_32	AC	2 ms 6,820 KB
testcase_33	AC	2 ms 6,816 KB
testcase_34	AC	3 ms 6,820 KB
testcase_35	AC	3 ms 6,820 KB
testcase_36	AC	3 ms 6,820 KB
testcase_37	AC	3 ms 6,820 KB
testcase_38	AC	3 ms 6,816 KB
testcase_39	AC	2 ms 6,820 KB
testcase_40	AC	2 ms 6,820 KB
testcase_41	AC	2 ms 6,820 KB
testcase_42	AC	2 ms 6,816 KB
testcase_43	AC	2 ms 6,820 KB
testcase_44	AC	2 ms 6,820 KB
testcase_45	AC	95 ms 8,112 KB
testcase_46	AC	97 ms 7,732 KB
testcase_47	AC	95 ms 8,020 KB
testcase_48	AC	86 ms 8,048 KB
testcase_49	AC	86 ms 8,020 KB
testcase_50	AC	84 ms 8,132 KB
testcase_51	AC	97 ms 8,164 KB
testcase_52	AC	91 ms 7,892 KB
testcase_53	AC	96 ms 8,076 KB
testcase_54	AC	99 ms 8,180 KB
testcase_55	AC	102 ms 8,160 KB
testcase_56	AC	98 ms 7,996 KB
testcase_57	AC	91 ms 7,724 KB
testcase_58	AC	94 ms 8,104 KB
testcase_59	AC	94 ms 8,240 KB
testcase_60	AC	88 ms 8,212 KB
testcase_61	AC	92 ms 8,188 KB
testcase_62	AC	90 ms 7,988 KB
testcase_63	AC	106 ms 8,108 KB
testcase_64	AC	97 ms 8,184 KB
testcase_65	AC	188 ms 7,780 KB
testcase_66	AC	205 ms 7,752 KB
testcase_67	AC	143 ms 9,916 KB
testcase_68	AC	138 ms 9,980 KB
testcase_69	AC	219 ms 10,028 KB
testcase_70	AC	167 ms 9,968 KB
testcase_71	AC	62 ms 6,820 KB
testcase_72	AC	61 ms 6,816 KB
testcase_73	AC	55 ms 6,820 KB
testcase_74	AC	66 ms 6,820 KB
testcase_75	AC	186 ms 9,904 KB
testcase_76	AC	143 ms 9,996 KB
testcase_77	AC	212 ms 9,828 KB
testcase_78	AC	233 ms 10,148 KB
testcase_79	AC	229 ms 10,112 KB
testcase_80	AC	168 ms 9,936 KB
testcase_81	AC	203 ms 9,912 KB
testcase_82	AC	166 ms 9,880 KB
testcase_83	AC	64 ms 6,820 KB
testcase_84	AC	61 ms 6,816 KB
testcase_85	AC	203 ms 9,988 KB
testcase_86	AC	185 ms 9,888 KB
testcase_87	AC	65 ms 10,036 KB
testcase_88	AC	61 ms 9,888 KB
testcase_89	AC	2 ms 6,820 KB
testcase_90	AC	2 ms 6,820 KB
testcase_91	AC	2 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <random>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
constexpr int MOD = 1000000007;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, -1, 1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p){os << "(" << p.first << ", " << p.second << ")"; return os;}

// WaveletMatrix<T> Tはデータ型
// verified: https://codeforces.com/contest/1042/submission/43071856
// N要素の配列Aに対する次のクエリを高速に処理する。メモリ使用量はO(N log max x) (max xはデータ型の最大値)
// 1. rank(k, x): Aの先頭から位置kまでに文字xがいくつあるか
// 2. select(n, x): n個目(1-origin)の文字xの次の位置はどこか
// 3. QuantileRange(l, r, n): 位置lと位置rの間で、n番目(1-origin)に小さい数は何か
// 4. RankLessThan(l, r, x): 位置lと位置rの間に、xと同じ数字が何個あるか, xより小さい数字が何個あるか, xより大きい数字が何個あるかを返す
// selectのみ時間がかかる(O(log N log max x))が、その他はO(log max x)で処理可能
// メモリ使用量: T = long long, N = 2*10^5 で 20MBくらい
// また、負の数は制御できない！Aの中やxに負の数が紛れ込まないようにしよう
// usage:
// vector<int> A(N); 
// WaveletMatrix<int> wm(A);

template<typename T>
struct WaveletMatrix {
    // FID
    // 手抜き実装のため、完備辞書にはなっていない (O(N)の追加領域が必要)
    struct FID {
        vector<uint32_t> bit;
        vector<int> acc;
        int N;
        FID(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]); 
            }
        }
        FID() {}
        // rank: 位置kまでに何個のxがあるかを返す
        // O(1)
        inline int rank(int k, int x = 1) {
            int n1 = acc[k >> 5] + __builtin_popcount(bit[k >> 5] & (uint32_t)(((1ULL << (k & 0x1f)) - 1)));
            return x ? n1 : k - n1;
        }

        // select: ビット列の先頭から見てn個目のxのビットの次の位置はどこか
        // O(log N)
        inline int select(int n, int x = 1) {
            int ng = 0, ok = N + 1;
            while(ok - ng > 1) {
                int c = (ok + ng) / 2;
                if (rank(c, x) >= n) {
                    ok = c;
                } else {
                    ng = c;
                }
            }
            return ok;
        }

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

        inline size_t size() {
            return N;
        }
    };

    vector<int> cntZero;
    vector<FID> bits;
    unordered_map<ll, int> pos;
    int level;
    ll mask;

    // rank
    // Aの先頭から位置kまでに文字xがいくつあるか
    // O(log max x)
    inline int rank(int k, T x) {
        int now = k;
        for(int j = level - 1; j >= 0; j--) {
            if (x >> j & 1) {
                now = cntZero[j] + bits[j].rank(now);
            } else {
                now = now - bits[j].rank(now);
            }
        }
        return now - pos[x ^ mask];
    }

    // select: 
    // n個目(1-origin)の文字xの次の位置はどこか
    // O(log N log max x)
    inline int select(int n, T x) {
        int now = pos[x ^ mask] + n;
        for(int j = 0; j < level; j++) {
            if (x >> j & 1) {
                int w = now - cntZero[j];
                now = bits[j].select(w);
            } else {
                now = bits[j].select(now, 0);
            }
        }
        return now;
    }

    // QuantileRange
    // 位置lと位置rの間で、n番目(1-origin)に小さい数は何か
    // 「数」と「その数と同じ数の中で、先頭から数えて何番目か」を返す
    // O(log max x)
    inline pair<T, int> QuantileRange(int l, int r, int n) {
        T ans = 0;
        for(int j = level - 1; j >= 0; j--) {
            ans <<= 1LL;
            int nz = bits[j].rank(r, 0) - bits[j].rank(l, 0);
            if (n > nz) {
                n -= nz;
                l = bits[j].rank(l, 1) + cntZero[j];
                r = bits[j].rank(r, 1) + cntZero[j];
                ans |= 1LL;
            } else {
                l = bits[j].rank(l, 0);
                r = bits[j].rank(r, 0);
            }
        }
        return {ans, l + n - pos[ans ^ mask]};
    }

    // RankLessThan
    // 位置lと位置rの間に、xと同じ数字が何個あるか, xより小さい数字が何個あるか, xより大きい数字が何個あるかを返す
    // tuple<int, int, int> ret = wm.RankLessThan(0, N, x); int eq = get<0>(ret), less = get<1>(ret), greater = get<2>(ret);
    // O(log max x)
    inline tuple<int, int, int> RankLessThan(int l, int r, T x) {
        T n_eq = 0, n_less = 0, n_greater = 0;
        for(int j = level - 1; j >= 0; j--) {
            if (x >> j & 1) {
                n_less += bits[j].rank(r, 0) - bits[j].rank(l, 0);
                l = bits[j].rank(l, 1) + cntZero[j];
                r = bits[j].rank(r, 1) + cntZero[j];
            } else {
                n_greater += bits[j].rank(r, 1) - bits[j].rank(l, 1);
                l = bits[j].rank(l, 0);
                r = bits[j].rank(r, 0);
            }
        }
        n_eq = r - l;
        return make_tuple(n_eq, n_less, n_greater);
    }

    WaveletMatrix(vector<T> A_) : level(sizeof(T) * 8) {
        cntZero.resize(level);
        bits.resize(level);
        vector<T> zero(A_.size());
        vector<T> one(A_.size());
        for(int j = level - 1; j >= 0; j--) {
            int n0 = 0, n1 = 0;
            vector<int> bit(A_.size());
            int cnt = 0;
            for(int i = 0; i < A_.size(); i++) {
                if (A_[i] >> j & 1) {
                    one[n1++] = A_[i];
                    bit[i] = 1;
                } else {
                    zero[n0++] = A_[i];
                    cnt++;
                }
            }
            vector<T> newA(zero.begin(), zero.begin() + n0);
            newA.insert(newA.end(), one.begin(), one.begin() + n1);
            A_ = std::move(newA);
            bits[j] = FID(bit);
            cntZero[j] = cnt;
        }
        //reverse(bits.begin(), bits.end());
        mask = random_device()();
        for(int i = 0; i < A_.size(); i++) {
            if (pos.find(A_[i]) == pos.end()) {
                pos[A_[i] ^ mask] = i;
            }
        }
    }

    void show() {
        cout << "cntZero: ";
        for (int i = 0; i < cntZero.size(); i++) {
            cout << cntZero[i] << ", ";
        }
        cout << endl;
        cout << "bits: " << endl;
        for (int j = 0; j < level; j++) {
            for (int i = 0; i < bits[j].size(); i++) {
                cout << bits[j][i] << ", ";
            }
            cout << endl;
        }
        cout << endl;
    }
};

void solve() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    WaveletMatrix<int> wm(A);
    int c_prev = wm.QuantileRange(0, K, (K + 1) / 2).first;
    ll sum = 0;
    for (int i = 0; i < K; i++) {
        sum += abs(A[i] - c_prev);
    }
    ll ans = sum;
    for(int i = K + 1; i <= N; i++) {
        int c = wm.QuantileRange(i - K, i, (K + 1) / 2).first;

        if (c != c_prev) {
            tuple<int,int,int> t1 = wm.RankLessThan(i - K , i - 1, c_prev);
            tuple<int,int,int> t2 = wm.RankLessThan(i - K , i - 1, c);
            if (c_prev > c) {
                int x1 = get<2>(t1) + get<0>(t1);
                int x2 = get<1>(t2) + get<0>(t2);
                sum += (c_prev - c) * (x1 - x2);
            } else {
                int x1 = get<1>(t1) + get<0>(t1);
                int x2 = get<2>(t2) + get<0>(t2);
                sum += (c - c_prev) * (x1 - x2);
            }
            
        }
        sum -= abs(A[i - K - 1] - c_prev);
        sum += abs(A[i - 1] - c);
        c_prev = c;
        ans = min(ans, sum);
    }
    cout << ans << endl;

}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}

yukicoder

結果

テストケース

ソースコード