Submission #1309266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309266		aaaaaaaa	Index (COCI21_index)	C++17	Compilation error	0 ms	0 KiB

index

#pragma GCC optimize("O3,unroll-loops,Ofast")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1, 0), cseen(q + 2, 0);

    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    map<int, set<int>> mp_l, mp_r;
    vector<int> st(q + 1, 0), en(q + 1, 0), p(q + 1, 0);
    vector<pair<int, int>> query;

    for(int i = 1, l, r; i <= q; ++i){
        cin >> l >> r;
        mp_l[l].insert(i);
        mp_r[r].insert(i);
        query.push_back({l, r});
        st[i] = 1, en[i] = n + 1;
        p[i] = (st[i] + en[i]) / 2;
    }
    
    vector<int> ans(q + 1, 0);

    for(int _ = 0; _ < 19; ++_){
        pbds oset;
        for(int i = 1; i <= n; ++i){
            for(auto it : mp_l[i]){
                if(st[it] > en[it]) {
                    cseen[it] = 0;
                    continue;
                }
                cseen[it] = -oset.order_of_key(p[it] - 1);
            }
            oset.insert(a[i]);
            for(auto it : mp_r[i]){
                if(st[it] > en[it]) {
                    cseen[it] = 0;
                    continue;
                }
                cseen[it] += oset.order_of_key(p[it] - 1);
                if(cseen[it] >= p[it]){
                    st[it] = p[it] + 1;
                    ans[it] = p[it];
                }else{
                    en[it] = p[it] - 1;
                }
                cseen[it] = 0;
            }
        }   
        for(int i = 1; i <= q; ++i){
            if(st[i] <= en[i]){
                p[i] = (st[i] + en[i]) / 2;
            }else{
                mp_l[query[i - 1].first].erase(i);
                mp_r[query[i - 1].second].erase(i);
            }
        }
    }

    for(int i = 1; i <= q; ++i) cout << ans[i] << "\n";
    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from index.cpp:3:
/usr/include/c++/13/bits/allocator.h: In destructor 'std::_Rb_tree<int, std::pair<const int, std::set<int> >, std::_Select1st<std::pair<const int, std::set<int> > >, std::less<int>, std::allocator<std::pair<const int, std::set<int> > > >::_Rb_tree_impl<std::less<int>, true>::~_Rb_tree_impl()':
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to 'always_inline' 'std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::_Rb_tree_node<std::pair<const int, std::set<int> > >]': target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/map:62,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:152:
/usr/include/c++/13/bits/stl_tree.h:662:16: note: called from here
  662 |         struct _Rb_tree_impl
      |                ^~~~~~~~~~~~~