#994797 (C++23(gcc13)) No.2809 Sort Query

提出ソース

結果

問題	No.2809 Sort Query
ユーザー	pitP
提出日時	2024-07-13 11:22:22
言語	C++23(gcc13) (gcc 13.2.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	13,810 bytes
コンパイル時間	9,278 ms
コンパイル使用メモリ	343,536 KB
実行使用メモリ	57,112 KB
最終ジャッジ日時	2024-07-13 11:23:11
合計ジャッジ時間	33,802 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,884 KB
testcase_01	TLE	-
testcase_02	TLE	-
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-
testcase_57	--	-
testcase_58	--	-
testcase_59	--	-
testcase_60	--	-
testcase_61	--	-
testcase_62	--	-
testcase_63	--	-
testcase_64	--	-
testcase_65	--	-
testcase_66	--	-
testcase_67	--	-
testcase_68	--	-
testcase_69	--	-
testcase_70	--	-

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

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }
istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }
istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } 

typedef long long ll;
typedef vector<vector<int>> Graph;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)
#define rep(i,n) for (int i = 0;i < (int)(n); i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define my_sort(x) sort(x.begin(), x.end())
#define my_max(x) *max_element(all(x))
#define my_min(x) *min_element(all(x))
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<62) - 1;
const int MOD = 998244353;
const int MOD2 = 1e9+7;
const double PI = acos(-1);
vector<int> di = {1,0,-1,0};
vector<int> dj = {0,1,0,-1};

#ifdef LOCAL
#  include <debug_print.hpp>
#  define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#  define debug(...) (static_cast<void>(0))
#endif

// T0: 元の配列のモノイド
// T1: T0に対する作用素モノイド
template <class T0, class T1>
class BaseImplicitTreap {
    // T0上の演算、単位元
    virtual T0 f0(T0, T0) = 0;
    const T0 u0;
    // T1上の演算、単位元
    virtual T1 f1(T1, T1) = 0;
    const T1 u1;
    // T0に対するT1の作用
    virtual T0 g(T0, T1) = 0;
    // 多数のt1(T1)に対するf1の合成
    virtual T1 p(T1, int) = 0;

    class xorshift {
        uint64_t x;

    public:
        xorshift() {
            mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
            x = rnd();
            for (int i = 0; i < 100; i++) {
                random();
            }
        }

        uint64_t random() {
            x = x ^ (x << 7);
            return x = x ^ (x >> 9);
        }
    } rnd;

    struct Node {
        T0 value, acc;
        T1 lazy;
        int priority, cnt;
        bool rev;
        Node *l, *r;

        Node(T0 value_, int priority_, T0 u0_, T1 u1_)
            : value(value_), acc(u0_), lazy(u1_), priority(priority_), cnt(1), rev(false), l(nullptr), r(nullptr) {}
    } *root = nullptr;

    using Tree = Node *;

    int cnt(Tree t) { return t ? t->cnt : 0; }

    T0 acc(Tree t) { return t ? t->acc : u0; }

    void update_cnt(Tree t) {
        if (t) {
            t->cnt = 1 + cnt(t->l) + cnt(t->r);
        }
    }

    void update_acc(Tree t) {
        if (t) {
            t->acc = f0(acc(t->l), f0(t->value, acc(t->r)));
        }
    }

    void pushup(Tree t) { update_cnt(t), update_acc(t); }

    void pushdown(Tree t) {
        if (t && t->rev) {
            t->rev = false;
            swap(t->l, t->r);
            if (t->l) t->l->rev ^= 1;
            if (t->r) t->r->rev ^= 1;
        }
        if (t && t->lazy != u1) {
            if (t->l) {
                t->l->lazy = f1(t->l->lazy, t->lazy);
                t->l->acc = g(t->l->acc, p(t->lazy, cnt(t->l)));
            }
            if (t->r) {
                t->r->lazy = f1(t->r->lazy, t->lazy);
                t->r->acc = g(t->r->acc, p(t->lazy, cnt(t->r)));
            }
            t->value = g(t->value, p(t->lazy, 1));
            t->lazy = u1;
        }
        pushup(t);
    }

    void split(Tree t, int key, Tree &l, Tree &r) {
        if (!t) {
            l = r = nullptr;
            return;
        }
        pushdown(t);
        int implicit_key = cnt(t->l) + 1;
        if (key < implicit_key) {
            split(t->l, key, l, t->l), r = t;
        } else {
            split(t->r, key - implicit_key, t->r, r), l = t;
        }
        pushup(t);
    }

    void insert(Tree &t, int key, Tree item) {
        Tree t1, t2;
        split(t, key, t1, t2);
        merge(t1, t1, item);
        merge(t, t1, t2);
    }

    void merge(Tree &t, Tree l, Tree r) {
        pushdown(l);
        pushdown(r);
        if (!l || !r) {
            t = l ? l : r;
        } else if (l->priority > r->priority) {
            merge(l->r, l->r, r), t = l;
        } else {
            merge(r->l, l, r->l), t = r;
        }
        pushup(t);
    }

    void erase(Tree &t, int key) {
        Tree t1, t2, t3;
        split(t, key + 1, t1, t2);
        split(t1, key, t1, t3);
        merge(t, t1, t2);
    }

    void update(Tree t, int l, int r, T1 x) {
        if (l >= r) return;
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2, t3);
        t2->lazy = f1(t2->lazy, x);
        t2->acc = g(t2->acc, p(x, cnt(t2)));
        merge(t2, t2, t3);
        merge(t, t1, t2);
    }

    T0 query(Tree t, int l, int r) {
        if (l == r) return u0;
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2, t3);
        T0 ret = t2->acc;
        merge(t2, t2, t3);
        merge(t, t1, t2);
        return ret;
    }

    // [l, r)の中で左から何番目か
    int find(Tree t, T0 x, int offset, bool left = true) {
        if (f0(t->acc, x) == x) {
            return -1;
        } else {
            if (left) {
                if (t->l && f0(t->l->acc, x) != x) {
                    return find(t->l, x, offset, left);
                } else {
                    return (f0(t->value, x) != x) ? offset + cnt(t->l) : find(t->r, x, offset + cnt(t->l) + 1, left);
                }
            } else {
                if (t->r && f0(t->r->acc, x) != x) {
                    return find(t->r, x, offset + cnt(t->l) + 1, left);
                } else {
                    return (f0(t->value, x) != x) ? offset + cnt(t->l) : find(t->l, x, offset, left);
                }
            }
        }
    }

    void reverse(Tree t, int l, int r) {
        if (l > r) return;
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2, t3);
        t2->rev ^= 1;
        merge(t2, t2, t3);
        merge(t, t1, t2);
    }

    // [l, r)の先頭がmになるようにシフトさせる。std::rotateと同じ仕様
    void rotate(Tree t, int l, int m, int r) {
        reverse(t, l, r);
        reverse(t, l, l + r - m);
        reverse(t, l + r - m, r);
    }

    void dump(Tree t) {
        if (!t) return;
        pushdown(t);
        dump(t->l);
        cout << t->value << " ";
        dump(t->r);
    }

public:
    BaseImplicitTreap(T0 u0_, T1 u1_) : u0(u0_), u1(u1_) {}

    void set_by_vector(const vector<T0> &a) {
        for (int i = 0; i < a.size(); i++) {
            insert(i, a[i]);
        }
    }

    int size() { return cnt(root); }

    void insert(int pos, T0 x) { insert(root, pos, new Node(x, rnd.random(), u0, u1)); }

    void update(int l, int r, T1 x) { update(root, l, r, x); }

    T0 query(int l, int r) { return query(root, l, r); }

    // 二分探索。[l, r)内のkでf0(tr[k], x) != xとなる最左/最右のもの。存在しない場合は-1
    // たとえばMinMonoidの場合、x未満の最左/最右の要素の位置を返す
    int binary_search(int l, int r, T0 x, bool left = true) {
        if (l >= r) return -1;
        Tree t1, t2, t3;
        split(root, l, t1, t2);
        split(t2, r - l, t2, t3);
        int ret = find(t2, x, l, left);
        merge(t2, t2, t3);
        merge(root, t1, t2);
        return ret;
    }

    void erase(int pos) { erase(root, pos); }

    void reverse(int l, int r) { reverse(root, l, r); }

    void rotate(int l, int m, int r) { rotate(root, l, m, r); }

    void dump() {
        dump(root);
        cout << endl;
    }

    T0 operator[](int pos) { return query(pos, pos + 1); }
};

template <class T0, class T1>
struct MinUpdateQuery : public BaseImplicitTreap<T0, T1> {
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    MinUpdateQuery() : MinUpdateQuery(numeric_limits<T0>::max(), numeric_limits<T1>::min()) {}
    T0 f0(T0 x, T0 y) override { return min(x, y); }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T1 p(T1 x, int len) override { return x; }
};

template <class T0, class T1>
struct MaxUpdateQuery : public BaseImplicitTreap<T0, T1> {
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    MaxUpdateQuery() : MaxUpdateQuery(numeric_limits<T0>::min(), numeric_limits<T1>::max()) {}
    T0 f0(T0 x, T0 y) override { return max(x, y); }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::max() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::max() ? x : y; }
    T1 p(T1 x, int len) override { return x; }
};

template <class T0, class T1>
struct SumAddQuery : public BaseImplicitTreap<T0, T1> {
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    SumAddQuery() : SumAddQuery(0, 0) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return x + y; }
    T0 g(T0 x, T1 y) override { return x + y; }
    T1 p(T1 x, int len) override { return x * len; }
};

template <class T0, class T1>
struct MinAddQuery : public BaseImplicitTreap<T0, T1> {
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    MinAddQuery() : MinAddQuery(numeric_limits<T0>::max(), 0) {}
    T0 f0(T0 x, T0 y) override { return min(x, y); }
    T1 f1(T1 x, T1 y) override { return x + y; }
    T0 g(T0 x, T1 y) override { return x + y; }
    T1 p(T1 x, int len) override { return x; }
};

template <class T0, class T1>
struct MaxAddQuery : public BaseImplicitTreap<T0, T1> {
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    MaxAddQuery() : MaxAddQuery(numeric_limits<T0>::min(), 0) {}
    T0 f0(T0 x, T0 y) override { return max(x, y); }
    T1 f1(T1 x, T1 y) override { return x + y; }
    T0 g(T0 x, T1 y) override { return x + y; }
    T1 p(T1 x, int len) override { return x; }
};

template <class T0, class T1>
struct SumUpdateQuery : public BaseImplicitTreap<T0, T1> {
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    SumUpdateQuery() : SumUpdateQuery(0, numeric_limits<T1>::min()) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T1 p(T1 x, int len) override { return x == numeric_limits<T1>::min() ? numeric_limits<T1>::min() : x * len; }
};

template <class T0>
struct SumAffineQuery : public BaseImplicitTreap<T0, pair<T0, T0>> {
    using T1 = pair<T0, T0>;  // first * x + second
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    SumAffineQuery() : SumAffineQuery(0, {1, 0}) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; }
    T0 g(T0 x, T1 y) override { return y.first * x + y.second; }
    T1 p(T1 x, int len) override { return {x.first, x.second * len}; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};

template <class T>
struct MinmaxAffineQuery : public BaseImplicitTreap<pair<T, T>, pair<T, T>> {
    using T0 = pair<T, T>;  // {min, max}
    using T1 = pair<T, T>;  // first * x + second
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    MinmaxAffineQuery()
        : MinmaxAffineQuery({numeric_limits<T>::max(), -numeric_limits<T>::max()}, {1, 0}) {
    }  // TODO: _u1を使うとコンパイル通らない原因不明
    T0 f0(T0 x, T0 y) override { return {min(x.first, y.first), max(x.second, y.second)}; }
    T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; }
    T0 g(T0 x, T1 y) override {
        T0 ret = {x.first * y.first + y.second, x.second * y.first + y.second};
        if (y.first < 0) swap(ret.first, ret.second);
        return ret;
    }
    T1 p(T1 x, int len) override { return x; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};
// https://xuzijian629.hatenablog.com/entry/2019/10/25/234938


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int N, Q; cin >> N >> Q;
    vector<ll> A(N + 2);
    A[0] = -LINF;
    A[N + 1] = LINF;
    rep(i, N) cin >> A[i + 1];

    MaxUpdateQuery<ll, ll> tree;
    tree.set_by_vector(A);

    vector<int> lazy;
    FOR(i, 1, N + 1) lazy.push_back(i);

    while(Q--){
        int op; cin >> op;
        if(op == 1){
            int k; cin >> k;
            ll x; cin >> x;
            tree.erase(k);
            tree.insert(k, x);
            lazy.push_back(k);
        }
        if(op == 2){
            sort(all(lazy));
            lazy.erase(unique(all(lazy)), lazy.end());
            reverse(all(lazy));

            vector<ll> vs;
            for(auto &x : lazy){
                vs.push_back(tree[x]);
                tree.erase(x);
            }

            for(auto &v : vs){
                int idx = tree.binary_search(0, (int)tree.size(), v, true);
                tree.insert(idx, v);
                // tree.dump();
            }

            lazy.clear();
        }
        if(op == 3){
            int k; cin >> k;
            cout << tree[k] << endl;
        }
    }
}

yukicoder

結果

テストケース

ソースコード