Submission #1309321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309321		aaaaaaaa	Index (COCI21_index)	C++17	60 / 110	2599 ms	69932 KiB

index

#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;
const int mxN = 2e5 + 10;
int a[mxN], cseen[mxN], st[mxN], en[mxN], p[mxN], seg[mxN * 2], ans[mxN];
map<int, set<int>> mp_l, mp_r;
vector<pair<int, int>> query;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, q, mx = 0;
    cin >> n >> q;

    unordered_set<int> seen;

    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        seen.insert(a[i]);
        mx = max(mx, a[i]);
    }

    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;
    }
    
    auto add = [&](int idx, int v) -> void {
        idx += mx - 1;
        seg[idx] += v;
        while(idx > 1){
            idx >>= 1;
            seg[idx] = seg[idx << 1] + seg[idx << 1 | 1];
        }
    };

    auto rem = [&](int idx) -> void {
        idx += mx - 1;
        seg[idx] = 0;
        while(idx > 1){
            idx >>= 1;
            seg[idx] = seg[idx << 1] + seg[idx << 1 | 1];
        }
    };

    auto ask = [&](int l, int r) -> int {
        l += mx - 1, r += mx - 1;
        int ans = 0;
        while(l <= r){
            if(l & 1) ans += seg[l++];
            if(r & 1 ^ 1) ans += seg[r--];
            l >>= 1, r >>= 1;
        }
        return ans;
    };

    for(int _ = 0; _ < 18; ++_){
        for(int i = 1; i <= n; ++i){
            for(auto it : mp_l[i]){
                if(st[it] > en[it]) {
                    cseen[it] = 0;
                    continue;
                }
                cseen[it] = -ask(p[it], mx);
            }
            add(a[i], 1);
            for(auto it : mp_r[i]){
                if(st[it] > en[it]) {
                    cseen[it] = 0;
                    continue;
                }
                cseen[it] += ask(p[it], mx);
                if(cseen[it] >= p[it]){
                    st[it] = p[it] + 1;
                    ans[it] = p[it];
                }else{
                    en[it] = p[it] - 1;
                }
                cseen[it] = 0;
            }
        }   
        for(auto it : seen) rem(it);
        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;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 0 / 50