Submission #854853

#	Time	Username	Problem	Language	Result	Execution time	Memory
854853		anha3k25cvp	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2757 ms	87580 KiB

bubblesort2

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "bubblesort2.h"

using namespace std;

mt19937 rnd(chrono :: steady_clock :: now().time_since_epoch().count());

struct Treap {
    Treap *left = nullptr, *right = nullptr;
    int x, y, p, val, ma, siz = 1, lazy = 0;
    Treap (int _x = 0, int _p = 0, int _val = 0) : x(_x), y(rnd()), p(_p), val(_val), ma(_val) {};
    void push() {
        if (left != nullptr)
            left -> lazy += lazy;
        if (right != nullptr)
            right -> lazy += lazy;
        val += lazy;
        ma += lazy;
        lazy = 0;
    }
    void update() {
        push();
        if (left != nullptr)
            left -> push();
        if (right != nullptr)
            right -> push();
        ma = max({val, (left != nullptr ? left -> ma : val), (right != nullptr ? right -> ma : val)});
        siz = (left != nullptr ? left -> siz : 0) + (right != nullptr ? right -> siz : 0) + 1;
    }
};

int siz(Treap *t) {
    return t == nullptr ? 0 : t -> siz;
}

Treap* Merge(Treap *t1, Treap *t2) {
    if (t1 == nullptr)
        return t2;
    if (t2 == nullptr)
        return t1;
    t1 -> push();
    t2 -> push();
    if (t1 -> y > t2 -> y) {
        t1 -> right = Merge(t1 -> right, t2);
        t1 -> update();
        return t1;
    }
    t2 -> left = Merge(t1, t2 -> left);
    t2 -> update();
    return t2;
}

pair <Treap*, Treap*> split(Treap *t, int x, int p) {
    if (t == nullptr)
        return {nullptr, nullptr};
    t -> push();
    if (t -> x > x || (t -> x == x && t -> p >= p)) {
        auto a = split(t -> left, x, p);
        t -> left = a.nd;
        t -> update();
        return {a.st, t};
    }
    auto a = split(t -> right, x, p);
    t -> right = a.st;
    t -> update();
    return {t, a.nd};
}

void add(Treap *t, int val) {
    if (t != nullptr)
        t -> lazy += val;
}

Treap *root;

vector <int> countScans(vector <int> a, vector <int> x, vector <int> v){
	int n = a.size(), q = x.size();
    vector <II> b(n);
    for (int i = 0; i < n; i ++)
        b[i] = {a[i], i};
    sort(b.begin(), b.end());
    for (int i = 0; i < n; i ++)
        root = Merge(root, new Treap(b[i].st, b[i].nd, b[i].nd - i));
	vector <int> ans(q);
	for (int t = 0; t < q; t ++) {
        int pos = x[t], val = v[t];
        if (val < a[pos]) {
            auto za = split(root, val, pos), zb = split(za.nd, a[pos], pos), zc = split(zb.nd, a[pos], pos + 1);
            add(zb.st, -1);
            root = Merge(Merge(za.st, new Treap(val, pos, pos - siz(za.st))), Merge(zb.st, zc.nd));
        }
        else {
            auto za = split(root, a[pos], pos), zc = split(za.nd, a[pos], pos + 1), zb = split(zc.nd, val, pos);
            add(zb.st, 1);
            root = Merge(Merge(za.st, zb.st), Merge(new Treap(val, pos, pos - siz(za.st) - siz(zb.st)), zb.nd));
        }
        a[pos] = val;
        root -> push();
        ans[t] = root -> ma;
	}
	return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:88:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   88 |     for (int i = 0; i < n; i ++)
      |     ^~~
bubblesort2.cpp:90:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   90 |  vector <int> ans(q);
      |  ^~~~~~

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