Submission #1270811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270811		windowwife	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1408 ms	176364 KiB

bubblesort2

#ifndef rtgsp
#include "bubblesort2.h"
#endif // rtgsp

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 2, inf = 1e9;
int n, m, q, a[maxn], x[maxn], v[maxn];
vector<int> cmp, vals[maxn];
set<int> pos[maxn];
struct ST
{
    ll st[4*maxn], lazy[4*maxn];
    void build (int node, int l, int r)
    {
        if (l == r)
        {
            st[node] = - *pos[l].begin();
            return;
        }
        int m = (l + r)/2;
        build(2*node, l, m);
        build(2*node + 1, m + 1, r);
        st[node] = max(st[2*node], st[2*node + 1]);
    }
    void down (int node)
    {
        st[2*node] = st[2*node] + lazy[node];
        lazy[2*node] = lazy[2*node] + lazy[node];
        st[2*node + 1] = st[2*node + 1] + lazy[node];
        lazy[2*node + 1] = lazy[2*node + 1] + lazy[node];
        lazy[node] = 0;
    }
    void upd1 (int node, int l, int r, int idx, int val)
    {
        if (l == r)
        {
            st[node] = st[node] + val;
            return;
        }
        down(node);
        int m = (l + r)/2;
        if (idx <= m) upd1(2*node, l, m, idx, val);
        else upd1(2*node + 1, m + 1, r, idx, val);
        st[node] = max(st[2*node], st[2*node + 1]);
    }
    void upd2 (int node, int l, int r, int cl, int cr, int val)
    {
        if (cr < l || r < cl) return;
        if (cl <= l && r <= cr)
        {
            st[node] = st[node] + val;
            lazy[node] = lazy[node] + val;
            return;
        }
        down(node);
        int m = (l + r)/2;
        upd2(2*node, l, m, cl, cr, val);
        upd2(2*node + 1, m + 1, r, cl, cr, val);
        st[node] = max(st[2*node], st[2*node + 1]);
    }
    int get (int node, int l, int r, int idx)
    {
        if (l == r) return st[node];
        down(node);
        int m = (l + r)/2;
        if (idx <= m) return get(2*node, l, m, idx);
        else return get(2*node + 1, m + 1, r, idx);
    }
}st;
vector<int> countScans (vector<int> A, vector<int> X, vector<int> V)
{
    n = A.size();
    for (int i = 1; i <= n; i++) a[i] = A[i - 1];
    q = X.size();
    for (int i = 1; i <= q; i++)
    {
        x[i] = X[i - 1] + 1;
        v[i] = V[i - 1];
    }
    vector<int> S;
    S.clear();
    for (int i = 1; i <= n; i++) cmp.push_back(a[i]);
    for (int i = 1; i <= q; i++) cmp.push_back(v[i]);
    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
    for (int i = 1; i <= (int)cmp.size(); i++) pos[i].insert(inf);
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin() + 1;
        pos[a[i]].insert(-i);
    }
    for (int i = 1; i <= q; i++)
        v[i] = lower_bound(cmp.begin(), cmp.end(), v[i]) - cmp.begin() + 1;
    m = cmp.size();
    st.build(1, 1, m);
    for (int i = 1; i <= n; i++)
        st.upd2(1, 1, m, a[i], m, -1);
    for (int i = 1; i <= q; i++)
    {
        int prv = *pos[a[x[i]]].begin();
        pos[a[x[i]]].erase(-x[i]);
        int nxt = *pos[a[x[i]]].begin();
        if (nxt != prv) st.upd1(1, 1, m, a[x[i]], prv - nxt);
        st.upd2(1, 1, m, a[x[i]], m, 1);
        a[x[i]] = v[i];
        prv = *pos[a[x[i]]].begin();
        pos[a[x[i]]].insert(-x[i]);
        nxt = *pos[a[x[i]]].begin();
        if (nxt != prv) st.upd1(1, 1, m, a[x[i]], prv - nxt);
        st.upd2(1, 1, m, a[x[i]], m, -1);
        S.push_back(st.st[1]);
    }
    return S;
}

#ifdef rtgsp
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    vector<int> A, X, V;
    A.clear(); X.clear(); V.clear();
    cin >> N >> Q;
    for (int i = 1; i <= N; i++)
    {
        int x;
        cin >> x;
        A.push_back(x);
    }
    for (int i = 1; i <= Q; i++)
    {
        int x;
        cin >> x;
        X.push_back(x);
    }
    for (int i = 1; i <= Q; i++)
    {
        int x;
        cin >> x;
        V.push_back(x);
    }
    auto S = countScans(A, X, V);
    for (int i : S) cout << i << '\n';
}
#endif // rtgsp

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