Submission #1290626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290626		baotoan655	Bubble Sort 2 (JOI18_bubblesort2)	C++20	0 / 100	61 ms	111664 KiB

bubblesort2

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int N = 1e6 + 5;

struct node {
    long long mx, lazy;
    node(long long _mx = 0, long long _lazy = 0) {
        mx = _mx;
        lazy = _lazy;
    }
    node operator + (const node& o) const {
        node res;
        res.mx = mx + o.mx;
        return res;
    }
} it[N << 2];

void upd(int k, long long val) {
    it[k].lazy += val;
    it[k].mx += val;
}
void shift(int k) {
    upd(k << 1, it[k].lazy);
    upd(k << 1 | 1, it[k].lazy);
    it[k].lazy = 0;
}
void update(int k, int l, int r, int u, int v, long long val) {
    if(l > v || r < u) return;
    if(u <= l && r <= v) {
        upd(k, val);
        return;
    }
    shift(k);
    int mid = l + r >> 1;
    update(k << 1, l, mid, u, v, val);
    update(k << 1 | 1, mid + 1, r, u, v, val);
    it[k] = it[k << 1] + it[k << 1 | 1];
}

set<int> s[N];

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
    int n = a.size(), q = x.size();
    vector<int> zip;
    for(int val : a) zip.emplace_back(val);
    for(int val : v) zip.emplace_back(val);
    sort(zip.begin(), zip.end());
    zip.resize(unique(zip.begin(), zip.end()) - zip.begin());
    auto id = [&](int val) -> int {
        return lower_bound(zip.begin(), zip.end(), val) - zip.begin() + 1;
    };

    int m = zip.size();
    for(int i = 1; i <= m; ++i) {
        s[i].insert(0);
    }
    for(int i = 0; i < n; ++i) {
        int val = id(a[i]);
        s[val].insert(i + 1);
        update(1, 1, m, val, m, -1);
    }
    for(int i = 1; i <= m; ++i) update(1, 1, m, i, i, *s[i].rbegin());
    vector<int> ans(q);
    for(int i = 0; i < q; ++i) {
        int v1 = id(a[x[i]]), v2 = id(v[i]);
        int tmp = *s[v1].rbegin();
        s[v1].erase(x[i] + 1);
        update(1, 1, m, v1, v1, *s[v1].rbegin() - tmp);

        tmp = *s[v2].rbegin();
        s[v2].insert(x[i] + 1);
        update(1, 1, m, v2, v2, *s[v2].rbegin() - tmp);

        update(1, 1, m, v1, m, 1);
        update(1, 1, m, v2, m, -1);
        ans[i] = it[1].mx;
        a[x[i]] = v[i];
    }
    return ans;
}

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