Submission #274496

#	Time	Username	Problem	Language	Result	Execution time	Memory
274496		johutha	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3409 ms	84068 KiB

bubblesort2

#include "bubblesort2.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

pair<int,int> merge(const pair<int,int>& p1, const pair<int,int>& p2)
{
    return make_pair(max(p1.first, p2.first), p1.second + p2.second);
}

struct segtree
{
    vector<pair<int,int>> table;
    vector<int> op;

    void apply(int pos, int o)
    {
        table[pos].first += o;
        op[pos] += o;
    }

    void propagate(int pos)
    {
        apply(2*pos + 1, op[pos]);
        apply(2*pos + 2, op[pos]);
        op[pos] = 0;
    }

    pair<int,int> query(int ql, int qr, int l, int r, int pos)
    {
        if (ql <= l && r <= qr) return table[pos];
        if (r < ql || qr < l) return {-1e8, 0};
        propagate(pos);
        return merge(query(ql, qr, l, (l + r)/2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2));
    }

    void update(int ql, int qr, int o, int l, int r, int pos)
    {
        if (ql <= l && r <= qr) { apply(pos, o); return; }
        if (r < ql || qr < l) return;
        propagate(pos);
        update(ql, qr, o, l, (l + r)/2, 2*pos + 1);
        update(ql, qr, o, (l + r)/2 + 1, r, 2*pos + 2);

        table[pos] = merge(table[2*pos + 1], table[2*pos + 2]);
    }

    void set(int k, int v, int l, int r, int pos)
    {
        if (l == r)
        {
            table[pos].first = v;
            table[pos].second = (v > -1e7);
            return;
        }
        propagate(pos);
        if (k <= (l + r)/2) set(k, v, l, (l + r)/2, 2*pos + 1);
        else set(k, v, (l + r)/2 + 1, r, 2*pos + 2);

        table[pos] = merge(table[2*pos + 1], table[2*pos + 2]);
    }
};


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

	vector<pair<int,int>> comp;
	
	for (int i = 0; i < n; i++) comp.emplace_back(a[i], i);
	for (int i = 0; i < q; i++) comp.emplace_back(v[i], x[i]);

	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());

	for (int i = 0; i < n; i++) a[i] = lower_bound(comp.begin(), comp.end(), make_pair(a[i], i)) - comp.begin();
	for (int i = 0; i < q; i++) v[i] = lower_bound(comp.begin(), comp.end(), make_pair(v[i], x[i])) - comp.begin();

	int vs = comp.size();

	segtree st;
	st.op.resize(4*vs);
	st.table.resize(4*vs, {-1e8, 0});

    auto insert = [&](int pos, int ind)
    {
        int lf = st.query(0, ind - 1, 0, vs - 1, 0).second;
        st.update(ind + 1, vs - 1, -1, 0, vs - 1, 0);
        st.set(ind, pos - lf, 0, vs - 1, 0);
    };

    auto remove = [&](int ind)
    {
        st.update(ind + 1, vs - 1, 1, 0, vs - 1, 0);
        st.set(ind, -1e8, 0, vs - 1, 0);
    };

    for (int i = 0; i < n; i++)
    {
        insert(i, a[i]);
    }

    vector<int> res;
    for (int i = 0; i < q; i++)
    {
        remove(a[x[i]]);
        insert(x[i], v[i]);
        a[x[i]] = v[i];
        res.push_back(st.query(0, vs - 1, 0, vs - 1, 0).first);
    }
    return res;
}

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