Submission #884035

#	Time	Username	Problem	Language	Result	Execution time	Memory
884035		vjudge1	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	71 ms	2588 KiB

bubblesort2

#include "./bubblesort2.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <climits>
using namespace std;

namespace pbds = __gnu_pbds;

template<typename T>
using ordered_tree = pbds::tree<T, pbds::null_type, less<T>, pbds::rb_tree_tag, pbds::tree_order_statistics_node_update>;

constexpr long long sqrt_ceil(long long n) {
    long long b = 1, e = n;
    while (b < e) {
        long long m = (b + e) / 2;
        if (m * m < n) b = m + 1;
        else e = m;
    }
    return b;
}

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v){

    int n = (int)a.size();
	int q = (int)x.size();

    vector<int> s(n + q);
    copy(a.begin(), a.end(), s.begin());
    copy(v.begin(), v.end(), s.begin() + n);
    sort(s.begin(), s.end());
    s.resize(unique(s.begin(), s.end()) - s.begin());
    vector<int> current_index(s.size());
    vector<int> id(n);

    auto get_id = [&](int val)->int& {
        return *lower_bound(current_index.begin(), current_index.end(), val);
    };

    int squirt = sqrt_ceil(n);

    vector<ordered_tree<pair<int, int>>> cox(squirt);
    
    for (int i = 0; i < n; i++) {
        int& curr_id = get_id(a[i]);
        cox[i / squirt].insert({a[i], curr_id});
        id[i] = curr_id;
        curr_id++;
    }

    vector<int> answer(q);
	for (int j = 0; j < q; j++) {
        int cnt = 0;
        int laba = x[j] / squirt;
        for (int i = 0; i < laba; i++) cnt -= (int)cox[i].size() - (int)cox[i].order_of_key({a[x[j]], INT_MAX});
        for (int i = laba + 1; i < (int)cox.size(); i++) cnt -= (int)cox[i].order_of_key({a[x[j]], 0});
        for (int i = 0; i < laba; i++) cnt += (int)cox[i].size() - (int)cox[i].order_of_key({v[j], INT_MAX});
        for (int i = laba + 1; i < (int)cox.size(); i++) cnt += (int)cox[i].order_of_key({v[j], 0});
        for (int i = laba * squirt; i < min(n, (laba + 1) * squirt); i++) {
            cnt -= i < x[j] && a[i] > a[x[j]];
            cnt -= i > x[j] && a[i] < a[x[j]];
            cnt += i < x[j] && a[i] > v[j];
            cnt += i > x[j] && a[i] < v[j];
        }
        cox[laba].erase(cox[laba].lower_bound({a[x[j]], 0}));
        int& curr_id = get_id(v[j]);
        cox[laba].insert({v[j], curr_id});
        id[x[j]] = curr_id;
        curr_id++;
        answer[j] = cnt;
        a[x[j]] = v[j];
	}

	return answer;
}

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