Submission #1285190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285190		nottete	Bubble Sort 2 (JOI18_bubblesort2)	C++20	0 / 100	50 ms	2404 KiB

bubblesort2

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

struct BIT {
    int n;
    vector<int> v;

    BIT(int n) : n(n), v(n) {}
    BIT() {}

    int sum(int r) {
        int res = 0;
        for(; r >= 0; r = (r & (r + 1)) - 1) res += v[r];
        return res;
    }

    int sum_r(int l) {
        int r = sum(n - 1);
        if(l > 0) r -= sum(l - 1);
        return r;
    }

    void add(int idx, int x) {
        for(; idx < n; idx = idx | (idx + 1)) v[idx] += x;
    }
};

struct Point {
    int idx;
    int val;
    int cnt;
    int j;
};

vector<int> sol;
vector<Point> pts;
int n;
int m;
BIT t;

bool cmp1(pair<int,Point>& p1, pair<int,Point>& p2) {
    if(p1.second.idx != p2.second.idx) return p1.second.idx > p2.second.idx;
    if(p1.second.val != p2.second.val) return p1.second.val < p2.second.val;
    return p1.first < p2.first;
}

bool cmp2(pair<int,Point>& p1, pair<int,Point>& p2) {
    if(p1.second.idx != p2.second.idx) return p1.second.idx < p2.second.idx;
    if(p1.second.val != p2.second.val) return p1.second.val > p2.second.val;
    return p1.first < p2.first;
}

void solve1(int l, int r) {
    if(l == r) return;

    int mid = (l + r) / 2;
    solve1(l, mid);
    solve1(mid + 1, r);

    vector<pair<int,Point>> tmp;
    for(int i = l; i <= mid; i++) {
        tmp.push_back({-1, pts[i]});
    }
    for(int i = mid+1; i <= r; i++) {
        tmp.push_back({1, pts[i]});
    }
    sort(tmp.begin(), tmp.end(), cmp1);

    vector<pair<int,int>> updates;

    for(auto[s, p] : tmp) {
        if(s == -1) {
            //cout << "ADD: " << p.idx << " " << p.val << " | " << p.cnt << " " << p.j << "\n";
            t.add(p.val, p.cnt);
            updates.push_back({p.val, p.cnt});
        } else {
            //cout << "QUE: " << p.idx << " " << p.val << " | " << p.cnt << " " <<  t.sum(p.val - 1)  << " " << p.j << "\n";
            sol[p.j] += p.cnt * t.sum(p.val - 1);
        }
    }
    //cout << "=============" <<  l << " " << r << "===============\n";
    for(auto[idx, x] : updates) {
        t.add(idx, -x);
    }
}

void solve2(int l, int r) {
    if(l == r) return;

    int mid = (l + r) / 2;
    solve2(l, mid);
    solve2(mid + 1, r);

    vector<pair<int,Point>> tmp;
    for(int i = l; i <= mid; i++) {
        tmp.push_back({-1, pts[i]});
    }
    for(int i = mid+1; i <= r; i++) {
        tmp.push_back({1, pts[i]});
    }
    sort(tmp.begin(), tmp.end(), cmp2);

    vector<pair<int,int>> updates;

    for(auto[s, p] : tmp) {
        if(s == -1) {
            //cout << "ADD: " << p.idx << " " << p.val << " | " << p.cnt << " " << p.j << "\n";
            t.add(p.val, p.cnt);
            updates.push_back({p.val, p.cnt});
        } else {
            //cout << "QUE: " << p.idx << " " << p.val << " | " << p.cnt << " " <<  t.sum_r(p.val + 1)  << " " << p.j << "\n";
            sol[p.j] += p.cnt * t.sum_r(p.val + 1);
        }
    }
    //cout << "=============" <<  l << " " << r << "===============\n";
    for(auto[idx, x] : updates) {
        t.add(idx, -x);
    }
}

vector<int> countScans(vector<int> arr, vector<int> x, vector<int> v) {
    vector<int> w = arr;
    n = arr.size();
    m = x.size();

    for(int i : v) {
        w.push_back(i);
    }

    sort(w.begin(), w.end());
    w.resize(unique(w.begin(), w.end()) - w.begin());

    for(int& i  : arr) {
        i = lower_bound(w.begin(), w.end(), i) - w.begin();
    }

    t = BIT(w.size());

    sol.assign(m + 1, {});
    pts.clear();
    pts.reserve(n + 2 * m);

    for(int i = 0; i < n; i++) {
        pts.push_back({
            .idx = i,
            .val = arr[i],
            .cnt = 1,
            .j = 0,
        });
    }

    for(int i = 0; i < m; i++) {
        int a = x[i];
        int b = lower_bound(w.begin(), w.end(), v[i]) - w.begin();
        bool s = b < v[i];
        pts.push_back({
            .idx = a,
            .val = arr[a],
            .cnt = -1,
            .j = i + 1,
        });

        arr[a] = b;

        pts.push_back({
            .idx = a,
            .val = arr[a],
            .cnt = 1,
            .j = i + 1,
        });
    }

    solve1(0, pts.size() - 1);
    solve2(0, pts.size() - 1);

    //for(int i : arr) cout << i << "\n";
    for(int i = 1; i < sol.size(); i++) {
        sol[i] += sol[i-1];
    }
    sol.erase(sol.begin());
    return sol;
}

// int main() {
//     vector<int> arr = {3, 2, 1, 4};
//     vector<int> x = {0, 2};
//     vector<int> v = {3, 1};

//     for (int i : countScans(arr, x, v)) {
//         cout << i << "\n";
//     };
// }

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