Submission #61735876

Source Code Expand

#include <vector>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cassert>

#include <iostream>

constexpr int bit_ceil_log(unsigned int n) {
    int x = 0;
    while ((1 << x) < (unsigned int)(n)) x++;
    return x;
}

template<typename T, typename cmp, T (*op)(T, T), T (*e)()>
struct partially_retroactive_priority_queue {
  private:
    static constexpr T null_val = std::numeric_limits<T>::max();
    static constexpr T _min(T a, T b) { return (b == null_val || (a != null_val && cmp()(a, b))) ? a : b; }
    static constexpr T _max(T a, T b) { return (a == null_val || (b != null_val && cmp()(a, b))) ? b : a; }
    enum optype { ERASED, CURRENT, POP, NONE };
    struct node {
        int Ce, Cc, Cp;
        int Dmin, mode;
        T Me, Mc;
        T x, sum;
        node() : Ce(0), Cc(0), Cp(0), Dmin(0), mode(NONE), Me(null_val), Mc(null_val), sum(e()) {}
    };
    void to_current(int _v) {
        node &v = d[_v];
        v.mode = CURRENT;
        v.Ce = v.Cp = v.Dmin = 0;
        v.Cc = 1;
        v.Me = null_val;
        v.Mc = v.x;
        v.sum = v.x;
        while (_v > 1) {
            _v /= 2;
            update(_v);
        }
    }
    void to_erased(int _v) {
        node &v = d[_v];
        v.mode = ERASED;
        v.Ce = v.Dmin = 1;
        v.Cc = v.Cp = 0;
        v.Me = v.x;
        v.Mc = null_val;
        v.sum = e();
        while (_v > 1) {
            _v /= 2;
            update(_v);
        }
    }
    void to_pop(int _v) {
        node &v = d[_v];
        v.mode = POP;
        v.Ce = v.Cc = 0;
        v.Cp = 1;
        v.Dmin = -1;
        v.Me = v.Mc = null_val;
        v.sum = e();
        while (_v > 1) {
            _v /= 2;
            update(_v);
        }
    }
    void to_none(int _v) {
        node &v = d[_v];
        v.mode = NONE;
        v.Ce = v.Cc = v.Cp = v.Dmin = 0;
        v.Me = v.Mc = null_val;
        v.x = v.sum = e();
        while (_v > 1) {
            _v /= 2;
            update(_v);
        }
    }

    int log, sz;
    std::vector<node> d;
    
    void update(int _v) {
        node &v = d[_v];
        node &l = d[_v * 2];
        node &r = d[_v * 2 + 1];
        v.Ce = l.Ce + r.Ce;
        v.Cc = l.Cc + r.Cc;
        v.Cp = l.Cp + r.Cp;
        v.Me = _max(l.Me, r.Me);
        v.Mc = _min(l.Mc, r.Mc);
        v.Dmin = std::min(l.Dmin, l.Ce - l.Cp + r.Dmin);
        v.sum = op(l.sum, r.sum);
    }

    template<bool lmost>
    int pos_dmin() const {
        int v = 1;
        while (v < sz) {
            int cnt = d[v * 2].Ce - d[v * 2].Cp;
            int RDmin = cnt + d[v * 2 + 1].Dmin;
            if (d[v * 2].Dmin < RDmin + lmost) {
                v = v * 2;
            } else {
                v = v * 2 + 1;
            }
        }
        return v - sz;
    }

    int pos_Mc(int r) const {
        int l = sz;
        r += sz;
        T Mc = null_val;
        while (l < r) {
            if (l & 1) Mc = _min(Mc, d[l++].Mc);
            if (r & 1) Mc = _min(Mc, d[--r].Mc);
            l >>= 1;
            r >>= 1;
        }
        int v = 1;
        while (v < sz) {
            bool is_l = (_min(d[v * 2].Mc, Mc) == d[v * 2].Mc);
            v = v * 2 + (!is_l);
        }
        return v - sz;
    }

    int pos_Me(int l) const {
        l += sz;
        int r = 2 * sz;
        T Me = null_val;
        while (l < r) {
            if (l & 1) Me = _max(Me, d[l++].Me);
            if (r & 1) Me = _max(Me, d[--r].Me);
            l >>= 1;
            r >>= 1;
        }
        int v = 1;
        while (v < sz) {
            bool is_r = (_max(d[v * 2 + 1].Me, Me) == d[v * 2 + 1].Me);
            v = v * 2 + is_r;
        }
        return v - sz;
    }

  public:
    partially_retroactive_priority_queue(int L) : log(bit_ceil_log(std::max(2, L))), sz(1 << log), d(2 * sz) {}

    void set_op_push(int k, T x) {
        assert(0 <= k && k < sz);
        set_op_null(k);
        d[sz + k].x = x;
        to_erased(sz + k);
        int l = (d[1].Dmin == 0 ? pos_dmin<false>() : 0);
        int p = pos_Me(l);
        to_current(sz + p);
    }

    // 空の状態でpopするような操作列に一度なると壊れる
    // あらかじめinfをQ個pushしておけばいい
    void set_op_pop(int k) {
        assert(0 <= k && k < sz);
        if (d[sz + k].mode == POP) return;
        set_op_null(k);
        to_pop(sz + k);
        int r = pos_dmin<true>();
        int p = pos_Mc(r);
        to_erased(sz + p);
    }

    void set_op_null(int k) {
        assert(0 <= k && k < sz);
        int mode = d[sz + k].mode;
        if (mode == NONE) return;
        to_none(k + sz);
        if (mode == ERASED) {
            int p = pos_dmin<true>();
            p = pos_Mc(p);
            to_erased(sz + p);
        }
        if (mode == POP) {
            int p = (d[1].Dmin == 0 ? pos_dmin<false>() : 0);
            p = pos_Me(p);
            to_current(sz + p);
        }
    }

    int size() const {
        return d[1].Cc;
    }

    bool empty() const {
        return size() == 0;
    }

    T top() const {
        assert(!empty());
        return d[1].Mc;
    }

    // 残っている要素の追加した時刻の順のprod
    T all_prod() const {
        return d[1].sum;
    }
};


/*
#include <iostream>
#include <set>

using S = uint64_t;
static constexpr S op(S a, S b) {
    return a + b;
}
static constexpr S e() {
    return 0;
}

using ppq = partially_retroactive_priority_queue<S, std::greater<S>, op, e>;

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int N, Q;
    std::cin >> N >> Q;
    
    std::vector<int> D(N), P(N), Dcnt(N, 0);
    std::vector<std::tuple<int, int, int>> QU(Q);
    for (int i = 0; i < N; i++) {
        std::cin >> D[i];
        D[i]--;
        Dcnt[D[i]]++;
    }
    for (int i = 0; i < N; i++) {
        std::cin >> P[i];
    }
    for (int i = 0; i < Q; i++) {
        int c, x, y;
        std::cin >> c >> x >> y;
        QU[i] = {c, x, y};
        Dcnt[x - 1]++;
    }
    ppq q(3 * N + Q);
    for (int i = 0; i < N; i++) q.set_op_push(i, 0);
    std::vector<std::set<int>> empty_pos(N);
    std::vector<int> used_pos(N);
    int p = N;
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < Dcnt[i]; j++) {
            empty_pos[i].insert(p + j);
        }
        p += Dcnt[i];
        q.set_op_pop(p++);
    }

    S allsum = 0;
    for (int i = 0; i < N; i++) {
        allsum += P[i];
        int d = D[i];
        auto itr = empty_pos[d].begin();
        used_pos[i] = *itr;
        q.set_op_push(*itr, P[i]);
        empty_pos[d].erase(itr);
    }
    for (int i = 0; i < Q; i++) {
        auto [c, x, y] = QU[i];
        c--, x--;
        int d = D[c];
        int p = used_pos[c];
        empty_pos[d].insert(p);
        q.set_op_null(p);
        allsum -= P[c];
        allsum += y;
        D[c] = x;
        P[c] = y;
        auto itr = empty_pos[x].begin();
        used_pos[c] = *itr;
        q.set_op_push(*itr, y);
        empty_pos[x].erase(itr);
        std::cout << (allsum - q.all_prod()) << '\n';
    }
}
*/


using S = long long;
static constexpr S op(S a, S b) {
    return a + b;
}
static constexpr S e() {
    return 0;
}

using ppq = partially_retroactive_priority_queue<S, std::greater<S>, op, e>;

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int N, M;
    std::cin >> N;
    M = N / 2;
    std::vector<long long> A(N);
    long long sum = 0;
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
        sum += A[i];
    }
    ppq pq(6 * M);
    for (int i = 0; i < M; i++) {
        int x = A[N - 2 * i - 1], y = A[N - 2 * i - 2];
        pq.set_op_push(i * 3, x);
        pq.set_op_push(i * 3 + 1, y);
        pq.set_op_pop(i * 3 + 2);
    }
    long long minsum = pq.all_prod(), mini = N;
    for (int i = 0; i < M - 1; i++) {
        int x = A[N - 2 * i - 1], y = A[N - 2 * i - 2];
        pq.set_op_null(i * 3 + 2);
        pq.set_op_null(i * 3 + 1);
        pq.set_op_null(i * 3);
        pq.set_op_push(3 * M + i * 3, x);
        pq.set_op_push(3 * M + i * 3 + 1, y);
        pq.set_op_pop(3 * M + i * 3 + 2);
        if (minsum > pq.all_prod()) {
            minsum = pq.all_prod();
            mini = 2 * (i + 1);
        }
    }
    std::cout << N - mini << " " << sum - minsum << '\n';
}

Submission Info

Submission Time
Task C - Rotate and Play Game
User tonegawa
Language C++ 23 (gcc 12.2)
Score 600
Code Size 8646 Byte
Status AC
Exec Time 449 ms
Memory 119300 KiB

Compile Error

Main.cpp: In function ‘constexpr int bit_ceil_log(unsigned int)’:
Main.cpp:11:21: warning: comparison of integer expressions of different signedness: ‘int’ and ‘unsigned int’ [-Wsign-compare]
   11 |     while ((1 << x) < (unsigned int)(n)) x++;
      |            ~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 23
Set Name Test Cases
Sample 00-sample-001.txt, 00-sample-002.txt, 00-sample-003.txt
All 00-sample-001.txt, 00-sample-002.txt, 00-sample-003.txt, 01-001.txt, 01-002.txt, 01-003.txt, 01-004.txt, 01-005.txt, 01-006.txt, 01-007.txt, 01-008.txt, 01-009.txt, 01-010.txt, 01-011.txt, 01-012.txt, 01-013.txt, 01-014.txt, 01-015.txt, 01-016.txt, 01-017.txt, 01-018.txt, 01-019.txt, 01-020.txt
Case Name Status Exec Time Memory
00-sample-001.txt AC 3 ms 3456 KiB
00-sample-002.txt AC 1 ms 3600 KiB
00-sample-003.txt AC 1 ms 3436 KiB
01-001.txt AC 360 ms 61876 KiB
01-002.txt AC 58 ms 17532 KiB
01-003.txt AC 278 ms 61400 KiB
01-004.txt AC 311 ms 61684 KiB
01-005.txt AC 317 ms 61656 KiB
01-006.txt AC 111 ms 32120 KiB
01-007.txt AC 5 ms 4124 KiB
01-008.txt AC 260 ms 61352 KiB
01-009.txt AC 213 ms 61080 KiB
01-010.txt AC 76 ms 17844 KiB
01-011.txt AC 444 ms 119300 KiB
01-012.txt AC 448 ms 119300 KiB
01-013.txt AC 443 ms 119180 KiB
01-014.txt AC 448 ms 119212 KiB
01-015.txt AC 445 ms 119168 KiB
01-016.txt AC 449 ms 119204 KiB
01-017.txt AC 442 ms 119160 KiB
01-018.txt AC 448 ms 119164 KiB
01-019.txt AC 443 ms 119176 KiB
01-020.txt AC 448 ms 119100 KiB