oj.uz

답안 #884028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
884028 2023-12-06T14:37:04 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 71 ms 2652 KB 
#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 int log2_ceil(int n) {
    int i = 0;
    while ((1 << i) < n) i++;
    return i;
}

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;
}


const int NMAX = 1 << log2_ceil(5e5);


int n, q;
int a[NMAX];
vector<ordered_tree<pair<int, int>>> cox;


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

    n = (int)a.size();
	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);

    cox = vector<ordered_tree<pair<int, int>>>(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;
	}

	return answer;
}

/*
int main() {

    #ifdef LOCAL
    freopen("file.in", "r", stdin);
    #endif

    int n, q;
    cin >> n >> q;
    vector<int> a(n), x(q), v(q);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> x[i] >> v[i];

    for (int r : countScans(a, x, v)) cout << r << '\n';

}

*/

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 71 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -