Submission #1335245


Source Code Expand

Copy
#include <cstdio>
#include <vector>
#include <algorithm>
#include <memory>
#include <stack>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;

constexpr int mod = 1e9+7;

ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (0 <= x and x < p);
    assert (0 <= y);
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
ll inv(ll x, ll p) { // p must be a prime, O(log p)
    assert ((x % p + p) % p != 0);
    return powmod(x, p-2, p);
}

template <class Monoid>
struct dynamic_segment_tree { // on monoid
    typedef Monoid monoid_type;
    typedef typename Monoid::type underlying_type;
    struct node_t {
        int left, right; // indices on pool
        underlying_type value;
    };
    deque<node_t> pool;
    int root; // index
    int width; // of the tree
    int size; // the number of leaves
    Monoid mon;
    dynamic_segment_tree(Monoid const & a_mon = Monoid()) : mon(a_mon) {
        node_t node = { -1, -1, mon.unit() };
        pool.push_back(node);
        root = 0;
        width = 1;
        size = 1;
    }
protected:
    int create_node(int parent, bool is_right) {
        // make a new node
        int i = pool.size();
        node_t node = { -1, -1, mon.unit() };
        pool.push_back(node);
        // link from the parent
        assert (parent != -1);
        int & ptr = is_right ? pool[parent].right : pool[parent].left;
        assert (ptr == -1);
        ptr = i;
        return i;
    }
    int get_value(int i) {
        return i == -1 ? mon.unit() : pool[i].value;
    }
public:
    void point_set(int i, underlying_type z) {
        assert (0 <= i);
        while (width <= i) {
            node_t node = { root, -1, pool[root].value };
            root = pool.size();
            pool.push_back(node);
            width *= 2;
        }
        point_set(root, -1, false, 0, width, i, z);
    }
    void point_set(int i, int parent, bool is_right, int il, int ir, int j, underlying_type z) {
        if (il == j and ir == j+1) { // 0-based
            if (i == -1) {
                i = create_node(parent, is_right);
                size += 1;
            }
            pool[i].value = z;
        } else if (ir <= j or j+1 <= il) {
            // nop
        } else {
            if (i == -1) i = create_node(parent, is_right);
            point_set(pool[i].left,  i, false, il, (il+ir)/2, j, z);
            point_set(pool[i].right, i, true,  (il+ir)/2, ir, j, z);
            pool[i].value = mon.append(get_value(pool[i].left), get_value(pool[i].right));
        }
    }
    underlying_type range_concat(int l, int r) {
        assert (0 <= l and l <= r);
        if (width <= l) return mon.unit();
        return range_concat(root, 0, width, l, min(width, r));
    }
    underlying_type range_concat(int i, int il, int ir, int l, int r) {
        if (i == -1) return mon.unit();
        if (l <= il and ir <= r) { // 0-based
            return pool[i].value;
        } else if (ir <= l or r <= il) {
            return mon.unit();
        } else {
            return mon.append(
                    range_concat(pool[i].left,  il, (il+ir)/2, l, r),
                    range_concat(pool[i].right, (il+ir)/2, ir, l, r));
        }
    }
    template <class Func>
    void traverse_leaves(Func func) {
        return traverse_leaves(root, 0, width, func);
    }
    template <class Func>
    void traverse_leaves(int i, int il, int ir, Func func) {
        if (i == -1) return;
        if (ir - il == 1) {
            func(il, pool[i].value);
        } else {
            traverse_leaves(pool[i].left,  il, (il+ir)/2, func);
            traverse_leaves(pool[i].right, (il+ir)/2, ir, func);
        }
    }
};

template <int mod>
struct modplus_t {
    typedef int type;
    int unit() const { return 0; }
    int append(int a, int b) const { int c = a + b; return c < mod ? c : c - mod; }
};

struct seq_t {
    int count;
    int delta;
    dynamic_segment_tree<modplus_t<mod> > segtree;
    int replicated;
};

void replicate(seq_t & a, int k, seq_t & b) {
    ll choose_k_2 = k *(ll) (k-1) % mod * inv(2, mod) % mod;
    b.count = (k *(ll) a.count % mod + choose_k_2 * a.delta % mod) % mod;
    b.delta = k *(ll) k % mod * a.delta % mod;
    b.segtree = move(a.segtree);
    b.replicated = k *(ll) a.replicated % mod;
}

void concatenate(seq_t & a, seq_t & b, seq_t & c) {
    ll count = a.count + b.count;
    ll delta = a.delta + b.delta;
    if (a.segtree.size < b.segtree.size) {
        int inv_b_replicated = inv(b.replicated, mod);
        int acc = 0;
        a.segtree.traverse_leaves([&](int i, int value) {
            value = a.replicated *(ll) value % mod;
            int gt_i = b.replicated *(ll) b.segtree.range_concat(i+1, max(i+1, b.segtree.width)) % mod;
            int eq_i = b.replicated *(ll) b.segtree.range_concat(i, i+1) % mod;
            int lt_i = b.replicated *(ll) b.segtree.range_concat(0, i) % mod;
            lt_i = (lt_i -(ll) acc + mod) % mod;
            count += lt_i *(ll) value % mod;
            delta += (gt_i + lt_i) % mod *(ll) value % mod;
            b.segtree.point_set(i, (eq_i +(ll) value) % mod * inv_b_replicated % mod);
            acc = (acc + value) % mod;
        });
        c.segtree = move(b.segtree);
        c.replicated = b.replicated;
    } else {
        int inv_a_replicated = inv(a.replicated, mod);
        int acc = 0;
        b.segtree.traverse_leaves([&](int i, int value) {
            value = b.replicated *(ll) value % mod;
            int gt_i = a.replicated *(ll) a.segtree.range_concat(i+1, max(i+1, a.segtree.width)) % mod;
            int eq_i = a.replicated *(ll) a.segtree.range_concat(i, i+1) % mod;
            int lt_i = a.replicated *(ll) a.segtree.range_concat(0, i) % mod;
            lt_i = (lt_i -(ll) acc + mod) % mod;
            count += gt_i *(ll) value % mod;
            delta += (gt_i + lt_i) % mod *(ll) value % mod;
            a.segtree.point_set(i, (eq_i +(ll) value) % mod * inv_a_replicated % mod);
            acc = (acc + value) % mod;
        });
        c.segtree = move(a.segtree);
        c.replicated = a.replicated;
    }
    c.count = count % mod;
    c.delta = delta % mod;
}

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> query(n); repeat (i,n) scanf("%d", &query[i]);
    // solve
    stack<shared_ptr<seq_t> > stk;
    for (int q : query) {
        if (q > 0) { // push
            shared_ptr<seq_t> a = make_shared<seq_t>();
            a->segtree.point_set(q-1, 1);
            a->replicated = 1;
            stk.push(a);
        } else if (q < 0) { // replicate
            assert (stk.size() >= 1);
            shared_ptr<seq_t> a = stk.top(); stk.pop();
            shared_ptr<seq_t> b = make_shared<seq_t>();
            replicate(*a, - q, *b);
            stk.push(b);
        } else { // concatenate
            assert (stk.size() >= 2);
            shared_ptr<seq_t> b = stk.top(); stk.pop();
            shared_ptr<seq_t> a = stk.top(); stk.pop();
            shared_ptr<seq_t> c = make_shared<seq_t>();
            concatenate(*a, *b, *c);
            stk.push(c);
        }
    }
    // output
    assert (stk.size() == 1);
    shared_ptr<seq_t> result = stk.top(); stk.pop();
    printf("%d\n", result->count);
    return 0;
}

Submission Info

Submission Time
Task D - バブルソート
User kimiyuki
Language C++14 (Clang 3.8.0)
Score 100
Code Size 7702 Byte
Status AC
Exec Time 617 ms
Memory 142464 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 50 / 50 50 / 50
Status
AC × 2
AC × 32
AC × 57
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
Subtask1 sample_01.txt, sample_02.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt
All sample_01.txt, sample_02.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt
Case Name Status Exec Time Memory
1_01.txt AC 2 ms 256 KB
1_02.txt AC 13 ms 3200 KB
1_03.txt AC 5 ms 1408 KB
1_04.txt AC 10 ms 384 KB
1_05.txt AC 9 ms 384 KB
1_06.txt AC 2 ms 256 KB
1_07.txt AC 11 ms 3072 KB
1_08.txt AC 5 ms 1280 KB
1_09.txt AC 7 ms 384 KB
1_10.txt AC 7 ms 384 KB
1_11.txt AC 2 ms 256 KB
1_12.txt AC 4 ms 3072 KB
1_13.txt AC 3 ms 1280 KB
1_14.txt AC 3 ms 384 KB
1_15.txt AC 3 ms 384 KB
1_16.txt AC 2 ms 256 KB
1_17.txt AC 13 ms 3200 KB
1_18.txt AC 5 ms 768 KB
1_19.txt AC 10 ms 384 KB
1_20.txt AC 9 ms 384 KB
1_21.txt AC 2 ms 256 KB
1_22.txt AC 13 ms 3200 KB
1_23.txt AC 5 ms 1280 KB
1_24.txt AC 10 ms 384 KB
1_25.txt AC 9 ms 472 KB
1_26.txt AC 1 ms 256 KB
1_27.txt AC 1 ms 256 KB
1_28.txt AC 1 ms 256 KB
1_29.txt AC 1 ms 256 KB
1_30.txt AC 1 ms 256 KB
2_01.txt AC 50 ms 640 KB
2_02.txt AC 617 ms 141568 KB
2_03.txt AC 200 ms 31488 KB
2_04.txt AC 606 ms 2816 KB
2_05.txt AC 508 ms 3328 KB
2_06.txt AC 53 ms 640 KB
2_07.txt AC 511 ms 142464 KB
2_08.txt AC 187 ms 56192 KB
2_09.txt AC 296 ms 896 KB
2_10.txt AC 279 ms 896 KB
2_11.txt AC 49 ms 640 KB
2_12.txt AC 181 ms 140980 KB
2_13.txt AC 72 ms 20480 KB
2_14.txt AC 74 ms 896 KB
2_15.txt AC 76 ms 896 KB
2_16.txt AC 51 ms 640 KB
2_17.txt AC 616 ms 142208 KB
2_18.txt AC 206 ms 51840 KB
2_19.txt AC 606 ms 2816 KB
2_20.txt AC 490 ms 2816 KB
2_21.txt AC 49 ms 640 KB
2_22.txt AC 615 ms 141312 KB
2_23.txt AC 177 ms 7296 KB
2_24.txt AC 610 ms 2816 KB
2_25.txt AC 504 ms 2816 KB
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB