Submission #1123443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123443		qrn	Index (COCI21_index)	C++20	60 / 110	2593 ms	64920 KiB

index

#include <bits/stdc++.h>
using namespace std;

template <class IStr, class T>
IStr &operator>>(IStr &is, vector<T> &v) {
    for (auto &x : v)
        is >> x;
    return is;
}

#define printt(a)          \
    for (auto v : a)      \
    {                     \
        cout << v << " "; \
    }                     \
    cout << endl;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
// #define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long
#define ins insert
#define vi vector<intt>
#define vpii vector<pair<intt, intt>>
#define vvi vector<vi>
#define pii pair<intt, intt>
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define impos cout << -1 << endl
#define fi first
#define se second

const int inf = 1e9 + 7, mxN = 2e5 + 5;

vector<vector<intt>>seg(4 * mxN);
vector<intt> a(mxN);

void merge(intt node) {
    for(intt i : seg[node*2]) {
        seg[node].pb(i);
    }
    for(intt i : seg[node*2+1]) {
        seg[node].pb(i);
    }
    sort(ALL(seg[node]));
}

void build(intt node, intt l, intt r) {
    if(l == r) {
        seg[node].pb(a[l]);
        return;
    }
    intt mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    merge(node);
}

intt ask(intt node, intt l, intt r, intt ql, intt qr, intt x) {
    if(ql > r || qr < l) {
       return 0;
    }
    
    if(ql <= l && r <= qr) {
        // if(ql == 5 && qr == 7){
        //     for(auto i : seg[node]) cout << i << " ";
        //     cout << "QOZ: " << l << " " << r << endl;
        //     cout << "POX: " << (lower_bound(ALL(seg[node]), x) - seg[node].begin()) << endl;
        // }
        return (r - l + 1) - (lower_bound(ALL(seg[node]), x) - seg[node].begin());
    }
    
    intt mid = (l + r) / 2;
    return (ask(node * 2, l, mid, ql, qr, x) +  ask(node * 2 + 1, mid + 1, r, ql, qr, x));
}

void solve() {
    intt n, q;
    cin >> n >> q;
    for(intt i = 1; i <= n; i++) cin >> a[i];
    
    build(1, 1, n);
      
    while(q--) {
        intt a, b;
        cin >> a >> b;
        intt l = 0, r = inf, ans = 0;
        while(l <= r) {
            intt mid = (l + r) / 2;
            intt cnt = ask(1, 1, n, a, b, mid);
            // if(a == 5 && b == 7)
            // cout << l << " " << r << " " << cnt << " " << mid << endl;
            if(cnt >= mid) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cout << ans << endl;
    }
}


int main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
    return 0;
}

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