Submission #1248613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248613		CodeLakVN	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1216 ms	53240 KiB

bubblesort2

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

#define task "main"
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)

const int MAX_N = (int)5e5 + 2;
const int INF = (int)1e8 + 1408;

struct IT {
    int tree[8 * MAX_N], lazy[8 * MAX_N];

    void apply(int id, int val) {
        tree[id] += val;
        lazy[id] += val;
    }

    void pushDown(int id) {
        if (lazy[id] == 0) return;
        apply(id << 1, lazy[id]);
        apply(id << 1 | 1, lazy[id]);
        lazy[id] = 0;
    }

    void update(int id, int l, int r, int pos, int itsVal, int othersVal) {
        if (l == r) {
            tree[id] += itsVal;
            return;
        }
        pushDown(id);
        int mid = (l + r) >> 1;
        if (pos <= mid) {
            apply(id << 1 | 1, othersVal);
            update(id << 1, l, mid, pos, itsVal, othersVal);
        }
        else update(id << 1 | 1, mid + 1, r, pos, itsVal, othersVal);
        tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
    }
} maxTree;

int ID(vector<ii> &arr, ii x) {
    return lower_bound(arr.begin(), arr.end(), x) - arr.begin() + 1;
}

vector<int> countScans(vector<int> a, vector<int> changePos, vector<int> newVals) {
    vector<ii> arr;
    int n = (int)a.size(), q = (int)changePos.size();
    FOR(i, 0, n - 1) arr.push_back({a[i], i});
    FOR(i, 0, q - 1) arr.push_back({newVals[i], changePos[i]});
    sort(arr.begin(), arr.end());
    arr.erase(unique(arr.begin(), arr.end()), arr.end());

    int sz = (int)arr.size();
    // we have to assign tree[i] = -INF to ensure that numbers that are not contained in the current array will not be computed
    FOR(i, 1, 4 * sz) maxTree.tree[i] = -INF, maxTree.lazy[i] = 0;

    FOR(i, 0, n - 1) {
        int pos = ID(arr, {a[i], i});
        maxTree.update(1, 1, sz, pos, i + INF, -1); // -INF + i + INF = i ==> this number is contained in the current array
    }

    vector<int> ans(q);
    FOR(i, 0, q - 1) {
        int pos = ID(arr, {a[changePos[i]], changePos[i]});
        maxTree.update(1, 1, sz, pos, -(changePos[i] + INF), +1); // remove this number
        a[changePos[i]] = newVals[i];
        pos = ID(arr, {a[changePos[i]], changePos[i]});
        maxTree.update(1, 1, sz, pos, changePos[i] + INF, -1);

        ans[i] = maxTree.tree[1];
    }

    return ans;
}

/* Lak lu theo dieu nhac!!!! */

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