Submission #1159825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159825		Der_Vlapos	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	2516 ms	104848 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(), v.end()

const int BIG = 1e9 + 10;

struct segTree
{
    vector<pii> tree;
    int sz = 0;

    void init(int n)
    {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.resize(2 * sz, {-BIG, 0});
    }

    void upd(int v, int val)
    {
        if (tree[v].f != -BIG)
        {
            tree[v].f += val;
            tree[v].s += val;
        }
    }

    void push(int v, int lv, int rv)
    {
        if (rv - lv == 1 or tree[v].s == 0)
            return;
        upd(v * 2 + 1, tree[v].s);
        upd(v * 2 + 2, tree[v].s);
        tree[v].s = 0;
    }

    void set(int pos, int val, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (rv - lv == 1)
        {
            tree[v].f = val;
            return;
        }
        int m = (lv + rv) >> 1;
        if (pos < m)
            set(pos, val, v * 2 + 1, lv, m);
        else
            set(pos, val, v * 2 + 2, m, rv);
        tree[v].f = max(tree[v * 2 + 1].f, tree[v * 2 + 2].f);
    }

    void set(int pos, int val)
    {
        set(pos, val, 0, 0, sz);
    }

    void add(int l, int r, int x, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (l <= lv and rv <= r)
        {
            upd(v, x);
            return;
        }
        if (rv <= l or r <= lv)
            return;
        int m = (lv + rv) >> 1;
        add(l, r, x, v * 2 + 1, lv, m);
        add(l, r, x, v * 2 + 2, m, rv);
        tree[v].f = max(tree[v * 2 + 1].f, tree[v * 2 + 2].f);
    }

    void add(int l, int r, int x)
    {
        add(l, r, x, 0, 0, sz);
    }
};

struct segTreeSum
{
    vector<ll> tree;
    int sz;

    void init(int n)
    {
        sz = n;
        tree.resize(2 * sz);
    }

    void build(vector<int> &a)
    {
        init(a.size());
        for (int i = 0; i < a.size(); ++i)
            tree[i + sz] = a[sz];

        for (int i = sz - 1; i > 0; --i)
            tree[i] = tree[i << 1] + tree[(i << 1) + 1];
    }

    int get(int l, int r) // [l, r)
    {
        l += sz;
        r += sz;
        int res = 0;

        while (l < r)
        {
            if (l & 1)
                res += tree[l++];
            if (r & 1)
                res += tree[--r];
            l >>= 1;
            r >>= 1;
        }

        return res;
    }

    void add(int pos, int val)
    {
        pos += sz;
        tree[pos] += val;
        pos >>= 1;
        while (pos)
        {
            tree[pos] = tree[pos << 1] + tree[(pos << 1) + 1];
            pos >>= 1;
        }
    }
};

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

    vector<int> VALS;
    for (int i = 0; i < n; ++i)
        VALS.pb(a[i]);
    for (int i = 0; i < q; ++i)
        VALS.pb(v[i]);
    sort(all(VALS));
    map<int, int> cnt;
    for (int i = 0; i < n; ++i)
        a[i] = lower_bound(all(VALS), a[i]) - VALS.begin() + (cnt[a[i]]++);
    for (int i = 0; i < q; ++i)
        v[i] = lower_bound(all(VALS), v[i]) - VALS.begin() + (cnt[v[i]]++);
    vector<int> l(VALS.size());
    vector<int> r(VALS.size());
    for (int p = 0; p < VALS.size(); ++p)
    {
        int curL = p;
        while (p + 1 < VALS.size() and VALS[p + 1] == VALS[p])
            p++;
        for (int j = curL; j <= p; ++j)
            l[j] = curL, r[j] = p;
    }

    segTree tree;
    segTreeSum cntEls;
    tree.init(VALS.size());
    cntEls.init(VALS.size());
    for (int i = 0; i < n; ++i)
    {
        // cerr << a[i] << " : " << i + 1 << "\n";
        tree.set(a[i], i + 1);
        cntEls.add(a[i], 1);
    }

    for (int i = 0; i < n; ++i)
    {
        // cerr << l[a[i]] << " " << VALS.size() << " : " << -1 << "\n";
        tree.add(l[a[i]], VALS.size(), -1);
    }

    for (int j = 0; j < q; j++)
    {
        int i = x[j];
        tree.set(a[i], -BIG);
        cntEls.add(a[i], -1);
        tree.add(l[a[i]], VALS.size(), 1);

        a[i] = v[j];

        tree.add(l[a[i]], VALS.size(), -1);
        cntEls.add(a[i], 1);
        tree.set(a[i], i + 1 - cntEls.get(0, r[a[i]] + 1));
        // tree.add(0, lower_bound(all(VALS), a[i]) - VALS.begin(), -1);
        answer[j] = tree.tree[0].f;
    }
    return answer;
}

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