oj.uz

Submission #884027

# Submission time Handle Problem Language Result Execution time Memory
884027 2023-12-06T14:36:08 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
Compilation error
 0 ms 0 KB 
#include "./bubblesort2.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
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';

}

*/

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:71:103: error: 'INT_MAX' was not declared in this scope
   71 |         for (int i = 0; i < laba; i++) cnt -= (int)cox[i].size() - (int)cox[i].order_of_key({a[x[j]], INT_MAX});
      |                                                                                                       ^~~~~~~
bubblesort2.cpp:6:1: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
    5 | #include <ext/pb_ds/assoc_container.hpp>
  +++ |+#include <climits>
    6 | #include <ext/pb_ds/tree_policy.hpp>
bubblesort2.cpp:71:111: error: cannot convert '<brace-enclosed initializer list>' to '__gnu_pbds::tree_order_statistics_node_update<__gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >, std::less<std::pair<int, int> >, std::allocator<char> >::key_const_reference' {aka 'const std::pair<int, int>&'}
   71 |         for (int i = 0; i < laba; i++) cnt -= (int)cox[i].size() - (int)cox[i].order_of_key({a[x[j]], INT_MAX});
      |                                                                                                               ^
In file included from /usr/include/c++/10/ext/pb_ds/tree_policy.hpp:149,
                 from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:48,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from bubblesort2.cpp:5:
/usr/include/c++/10/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp:79:34: note:   initializing argument 1 of '__gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::size_type __gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::order_of_key(__gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::key_const_reference) const [with Node_CItr = __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >; Node_Itr = __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >; Cmp_Fn = std::less<std::pair<int, int> >; _Alloc = std::allocator<char>; __gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::size_type = long unsigned int; __gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::key_const_reference = const std::pair<int, int>&]'
   79 | order_of_key(key_const_reference r_key) const
      |              ~~~~~~~~~~~~~~~~~~~~^~~~~
bubblesort2.cpp:73:100: error: 'INT_MAX' was not declared in this scope
   73 |         for (int i = 0; i < laba; i++) cnt += (int)cox[i].size() - (int)cox[i].order_of_key({v[j], INT_MAX});
      |                                                                                                    ^~~~~~~
bubblesort2.cpp:73:100: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
bubblesort2.cpp:73:108: error: cannot convert '<brace-enclosed initializer list>' to '__gnu_pbds::tree_order_statistics_node_update<__gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >, std::less<std::pair<int, int> >, std::allocator<char> >::key_const_reference' {aka 'const std::pair<int, int>&'}
   73 |         for (int i = 0; i < laba; i++) cnt += (int)cox[i].size() - (int)cox[i].order_of_key({v[j], INT_MAX});
      |                                                                                                            ^
In file included from /usr/include/c++/10/ext/pb_ds/tree_policy.hpp:149,
                 from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:48,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from bubblesort2.cpp:5:
/usr/include/c++/10/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp:79:34: note:   initializing argument 1 of '__gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::size_type __gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::order_of_key(__gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::key_const_reference) const [with Node_CItr = __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >; Node_Itr = __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >; Cmp_Fn = std::less<std::pair<int, int> >; _Alloc = std::allocator<char>; __gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::size_type = long unsigned int; __gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::key_const_reference = const std::pair<int, int>&]'
   79 | order_of_key(key_const_reference r_key) const
      |              ~~~~~~~~~~~~~~~~~~~~^~~~~