Submission #894075

#	Time	Username	Problem	Language	Result	Execution time	Memory
894075		box	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2196 ms	126064 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;

const int INF = 1e9;

struct segt {
    int l, r;
    segt *lc = NULL, *rc = NULL;
    int x, lz;
    segt(int l, int r) : l(l), r(r) {
        x = -INF, lz = 0;
        if (l < r) {
            int m = (l + r) / 2;
            lc = new segt(l, m);
            rc = new segt(m + 1, r);
        }
    }
    void put(int v) {
        x += v;
        lz += v;
    }
    void push() {
        if (lz != 0)
            lc->put(lz), rc->put(lz), lz = 0;
    }
    void add(int ql, int qr, int v) {
        if (ql <= l && qr >= r) put(v);
        else {
            push();
            if (qr <= lc->r) lc->add(ql, qr, v);
            else if (ql >= rc->l) rc->add(ql, qr, v);
            else lc->add(ql, qr, v), rc->add(ql, qr, v);
            x = max(lc->x, rc->x);
        }
    }
};

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
    vector<pii> v;
    for (int i = 0; i < sz(A); i++) v.push_back({A[i], i});
    for (int i = 0; i < sz(X); i++) v.push_back({V[i], X[i]});
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
    segt *tree = new segt(0, sz(v) - 1);
    auto del = [&](int i) {
        int p = lower_bound(begin(v), end(v), pii{A[i], i}) - begin(v);
        tree->add(p, p, -INF - i);
        if (p + 1 < sz(v)) tree->add(p + 1, sz(v) - 1, 1);
    };
    auto ins = [&](int i) {
        int p = lower_bound(begin(v), end(v), pii{A[i], i}) - begin(v);
        tree->add(p, p, INF + i);
        if (p + 1 < sz(v)) tree->add(p + 1, sz(v) - 1, -1);
    };
    for (int i = 0; i < sz(A); i++) ins(i);
    vector<int> ans(sz(X));
    for (int i = 0; i < sz(X); i++) {
        int p = X[i];
        del(p);
        A[p] = V[i];
        ins(p);
        ans[i] = tree->x;
    }
    return ans;
}

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