Submission #102474

#	Time	Username	Problem	Language	Result	Execution time	Memory
102474		minhtung0404	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	6756 ms	173664 KiB

bubblesort2

//https://oj.uz/problem/view/JOI18_bubblesort2

#include "bubblesort2.h"
#include<bits/stdc++.h>
const int N = 1e5 + 5;
const int MAX = 1e6 + 5;
const int inf = 1e9;
using namespace std;

map <int, int> mp;
typedef vector <int> vi;
multiset <int> ms[MAX];

int n, q, cnt, it[MAX << 2], lazy[MAX << 2], bit[MAX], offset[MAX];

void updateBIT(int i, int v){
    while (i < MAX){
        bit[i] += v;
        i += i&(-i);
    }
}

int getBIT(int i){
    int ans = 0;
    while (i > 0){
        ans += bit[i];
        i -= i&(-i);
    }
    return ans;
}

void dolazy(int i, int l, int r){
    if (!lazy[i]) return;
    if (l != r){
        lazy[i << 1] += lazy[i];
        lazy[i << 1 | 1] += lazy[i];
    }
    else{
        offset[l] += lazy[i];
    }
    it[i] += lazy[i];
    lazy[i] = 0;
}

void Insert(int i, int l, int r, int pos, int val){
    dolazy(i, l, r);
    if (l > pos || pos > r) return;
    if (l == r){
        ms[l].insert(val - offset[l]);
        if (ms[l].size()) it[i] = *ms[l].rbegin() + offset[l];
        else it[i] = -inf;
        return;
    }
    int mid = (l + r) >> 1;
    Insert(i << 1, l, mid, pos, val); Insert(i << 1 | 1, mid+1, r, pos, val);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void Erase(int i, int l, int r, int pos, int val){
    dolazy(i, l, r);
    if (l > pos || pos > r) return;
    if (l == r){
        ms[l].erase(ms[l].lower_bound(val - offset[l]));
        if (ms[l].size()) it[i] = *ms[l].rbegin() + offset[l];
        else it[i] = -inf;
        return;
    }
    int mid = (l + r) >> 1;
    Erase(i << 1, l, mid, pos, val); Erase(i << 1 | 1, mid+1, r, pos, val);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void update(int i, int l, int r, int L, int R, int v){
    dolazy(i, l, r);
    if (L > r || l > R) return;
    if (L <= l && r <= R){
        lazy[i] = v;
        dolazy(i, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, L, R, v); update(i << 1 | 1, mid+1, r, L, R, v);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

vi countScans(vi a, vi x, vi y){
    n = a.size(), q = x.size();
    vi ans(q);
    for (auto val : a) mp[val] = true;
    for (auto val : y) mp[val] = true;
    for (auto& p : mp) p.second = ++cnt;
    for (auto& val : a) val = mp[val], updateBIT(val, +1);
    for (auto& val : y) val = mp[val];
    for (int i = 0; i < MAX << 2; i++) it[i] = -inf;
    for (int i = 0; i < n; i++) Insert(1, 1, cnt, a[i], i+1-getBIT(a[i]));

    for (int i = 0; i < q; i++){
        Erase(1, 1, cnt, a[x[i]], x[i]+1-getBIT(a[x[i]]));
        update(1, 1, cnt, a[x[i]], cnt, +1);

        updateBIT(a[x[i]], -1);
        a[x[i]] = y[i];
        updateBIT(a[x[i]], +1);

        update(1, 1, cnt, a[x[i]], cnt, -1);
        Insert(1, 1, cnt, a[x[i]], x[i]+1-getBIT(a[x[i]]));
        ans[i] = it[1];
    }
    return ans;
}

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