Submission #400854

#	Time	Username	Problem	Language	Result	Execution time	Memory
400854		timmyfeng	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2429 ms	51432 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;

array<int, 2> values[N];
int maxi[4 * N], lazy[4 * N], m;

void update(int a, int b, int x, int u = 1, int l = 0, int r = m - 1) {
    if (a > b || b < l || r < a) {
        return;
    } else if (a <= l && r <= b) {
        lazy[u] += x;
        maxi[u] += x;
    } else {
        int m = (l + r) / 2;
        update(a, b, x, 2 * u, l, m);
        update(a, b, x, 2 * u + 1, m + 1, r);
        maxi[u] = max(maxi[2 * u], maxi[2 * u + 1]) + lazy[u];
    }
}

void assign(int a, int x, int u = 1, int l = 0, int r = m - 1) {
    if (l == r) {
        maxi[u] = x + lazy[u];
    } else {
        int m = (l + r) / 2;
        if (a <= m) {
            assign(a, x, 2 * u, l, m);
        } else {
            assign(a, x, 2 * u + 1, m + 1, r);
        }
        maxi[u] = max(maxi[2 * u], maxi[2 * u + 1]) + lazy[u];
    }
}

void insert(int a, int i, int k) {
    a = lower_bound(values, values + m, array<int, 2>{a, i}) - values;
    update(a + 1, m - 1, k);
    assign(a, k == 1 ? 0 : i);
}

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

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

    for (int i = 0; i < q; ++i) {
        values[n + i] = {v[i], x[i]};
    }

    sort(values, values + n + q);
    m = unique(values, values + n + q) - values;

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

    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        insert(a[x[i]], x[i], 1);
        a[x[i]] = v[i];
        insert(v[i], x[i], -1);
        ans[i] = maxi[1];
    }

    return ans;
}

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