Submission #128961

#	Time	Username	Problem	Language	Result	Execution time	Memory
128961		EntityIT	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2142 ms	89804 KiB

bubblesort2

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const int N = (int)5e5 + 5, Q = N, inf = (int)1e9 + 123;
int n, q, order_q[N], order_a[N];

struct It {
    struct Node {
        int cnt, mx, lz;
        Node (int _cnt = 0, int _mx = -inf, int _lz = 0) : cnt(_cnt), mx(_mx), lz(_lz) {}
        Node operator+ (const Node &_) const { return Node(cnt + _.cnt, max(mx, _.mx), 0); }
    } node[N << 3];
    void true_val (int nd, int Left, int Right) {
        if (!node[nd].lz) return ;
        node[nd].mx += node[nd].lz;
        if (Left != Right) {
            node[nd << 1].lz += node[nd].lz;
            node[nd << 1 | 1].lz += node[nd].lz;
        }
        node[nd].lz = 0;
    }
    void upd_rep (int nd, int Left, int Right, int pos, int val_mx, int val_cnt) {
        true_val(nd, Left, Right);
        if (pos < Left || Right < pos) return ;
        if (Left == Right) {
            node[nd] = Node(val_cnt, val_mx, 0);
            return ;
        }
        int mid = (Left + Right) >> 1;
        upd_rep(nd << 1, Left, mid, pos, val_mx, val_cnt);
        upd_rep(nd << 1 | 1, mid + 1, Right, pos, val_mx, val_cnt);
        node[nd] = node[nd << 1] + node[nd << 1 | 1];
    }
    void upd_add (int nd, int Left, int Right, int l, int r, int val) {
        true_val(nd, Left, Right);
        if (r < Left || Right < l) return ;
        if (l <= Left && Right <= r) {
            node[nd].lz = val; true_val(nd, Left, Right);
            return ;
        }
        int mid = (Left + Right) >> 1;
        upd_add(nd << 1, Left, mid, l, r, val);
        upd_add(nd << 1 | 1, mid + 1, Right, l, r, val);
        node[nd] = node[nd << 1] + node[nd << 1 | 1];
    }
    int get_cnt (int nd, int Left, int Right, int l, int r) {
        true_val(nd, Left, Right);
        if (r < Left || Right < l) return 0;
        if (l <= Left && Right <= r) return node[nd].cnt;
        int mid = (Left + Right) >> 1;
        return get_cnt(nd << 1, Left, mid, l, r) + get_cnt(nd << 1 | 1, mid + 1, Right, l, r);
    }
} it;

struct Vec_ele {
    int val, pos_a, dstnct;
    Vec_ele (int _val = 0, int _pos_a = 0, int _dstnct = 0) : val(_val), pos_a(_pos_a), dstnct(_dstnct) {}
    bool operator< (const Vec_ele &_) const { return make_pair(val, pos_a) < make_pair(_.val, _.pos_a); }
};

vector<int> countScans (vector<int> a, vector<int> x, vector<int> v) {
    n = (int)a.size(); q = (int)x.size();

    vector<Vec_ele> vec;
    for (int i = 0; i < n; ++i) vec.pb( Vec_ele(a[i], i, i) );
    for (int i = 0; i < q; ++i) vec.pb( Vec_ele(v[i], x[i], i + n) );
    sort(vec.begin(), vec.end() );

    for (int i = 0; i < (int)vec.size(); ++i) {
        int pos_a = vec[i].pos_a, dstnct = vec[i].dstnct;
        if (dstnct < n) {
            order_a[dstnct] = i;
            int up_val = pos_a - it.get_cnt(1, 0, (int)vec.size() - 1, 0, i);
            it.upd_rep(1, 0, (int)vec.size() - 1, order_a[dstnct], up_val, 1);
        }
        else order_q[dstnct - n] = i;
    }

    vector<int> ret(q);

    for (int i = 0; i < q; ++i) {
        it.upd_add(1, 0, (int)vec.size() - 1, order_a[ x[i] ], (int)vec.size() - 1, 1);
        it.upd_rep(1, 0, (int)vec.size() - 1, order_a[ x[i] ], -inf, 0);
        order_a[ x[i] ] = order_q[i];
        it.upd_add(1, 0, (int)vec.size() - 1, order_a[ x[i] ], (int)vec.size() - 1, -1);
        int up_val = x[i] - it.get_cnt(1, 0, (int)vec.size() - 1, 0, order_a[ x[i] ]);
        it.upd_rep(1, 0, (int)vec.size() - 1, order_a[ x[i] ], up_val, 1);
        ret[i] = it.node[1].mx;
    }

    return ret;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40