Submission #1295181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295181		tudor_costin	Bubble Sort 2 (JOI18_bubblesort2)	C++20	0 / 100	9095 ms	49296 KiB

bubblesort2

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int Nmax = 1e6 + 5;
const ll inf = 1e9;
struct node
{
    int cnt;
    ll maxval;
};
node unite(node st, node dr)
{
    node ans;
    ans.cnt = st.cnt + dr.cnt;
    ans.maxval = max(st.maxval + dr.cnt, dr.maxval);
    return ans;
}
int repr[Nmax];
node aint[4 * Nmax];
set < int > poz[Nmax];
void build(int nod, int l, int r)
{
    if (l == r)
    {
        if (repr[l] == 0)
        {
            aint[nod].cnt = poz[l].size();
            aint[nod].maxval = -inf;
        }
        else
        {
            aint[nod].cnt = poz[l].size();
            aint[nod].maxval = repr[l];
        }
        return;
    }
    int mid = (l + r) / 2;
    build(2 * nod, l, mid);
    build(2 * nod + 1, mid + 1, r);
    aint[nod] = unite(aint[2 * nod], aint[2 * nod + 1]);
    return;
}
void update(int nod, int l, int r, int x, int val)
{
    if (l == r)
    {
        if (val == 0)
        {
            aint[nod].cnt = poz[l].size();
            aint[nod].maxval = -inf;
        }
        else
        {
            aint[nod].cnt = poz[l].size();
            aint[nod].maxval = val;
        }
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid) update(2 * nod, l, mid, x, val);
    else update(2 * nod + 1, mid + 1, r, x, val);
    aint[nod] = unite(aint[2 * nod], aint[2 * nod + 1]);
    return;
}
vector < int > countScans(vector < int > a, vector < int > x, vector < int > v)
{
    int n = a.size(), q = x.size();
    map < int, vector < pair < int, int >>> nrm;
    for (int i = 0; i < n; i++) nrm[a[i]].push_back({
        i,
        0
    });
    for (int i = 0; i < q; i++) nrm[v[i]].push_back({
        i,
        1
    });
    int nrc = 0;
    for (auto[val, V]: nrm)
    {
        nrc++;
        for (auto[id, tip]: V)
        {
            if (tip == 0) a[id] = nrc;
            else v[id] = nrc;
        }
    }
    for (int i = 0; i < n; i++) poz[a[i]].insert(i + 1);
    for (int i = 1; i <= nrc; i++)
    {
        if (!poz[i].empty()) repr[i] = ( * poz[i].rbegin());
    }
    build(1, 1, nrc);
    vector < int > ans(q, 0);
    for (int i = 0; i < q; i++)
    {
        int cur = a[x[i]];
        poz[cur].erase(poz[cur].find(x[i] + 1));
        int nw;
        if (poz[cur].empty()) nw = 0;
        else nw = ( * poz[cur].rbegin());
        assert(cur <= nrc && v[i] <= nrc);
        update(1, 1, nrc, cur, nw);
        repr[cur] = nw;
        poz[v[i]].insert(x[i] + 1);
        nw = ( * poz[v[i]].rbegin());
        update(1, 1, nrc, v[i], nw);
        repr[v[i]] = nw;
        ans[i] = aint[1].maxval - n;
    }
    return ans;
}/*
int main()
{
    int n, q;
    cin >> n >> q;
    vector < int > a(n), x(q), v(q);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> x[i] >> v[i];
    vector < int > ans = countScans(a, x, v);
    for (int x: ans) cout << x << '\n';
    return 0;
}*/

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