Submission #1125033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125033		yavuzskarahan	Index (COCI21_index)	C++20	110 / 110	1196 ms	92536 KiB

index

// In the name of God, the Most Gracious, the Most Merciful.
// @yavuzskarahan - iflbot();
 
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0);
#define file(x) freopen(x ".in", "r", stdin); freopen(x ".out", "w", stdout);
#define FOR(i, L, R) for (int i = (L); i <= (R); i++)
#define SORT(v) sort((v).begin(), (v).end()) 
#define RSORT(v) sort((v).rbegin(), (v).rend()) 
#define int long long
#define ll long long
#define pb push_back
#define ub(v, a) upper_bound((v).begin(), (v).end(), (a))
#define lb(v, a) lower_bound((v).begin(), (v).end(), (a))
#define f first
#define s second
#define tm (tl+(tr-tl)/2)
#define space << " " <<
#define vi vector<int>
#define pii pair<int,int> 
#define vpii vector<pair<int,int>>
#define now chrono::high_resolution_clock::now()
 
const long long N = 2e5+5;
const long long M = 3e6+5;
 
const long long SQRTN = sqrt(N);
const long long MOD = 1e9+7;
inline int sum(int a, int b) {return ((a%MOD)+(b%MOD))%MOD;}
inline int mul(int a, int b) {return ((a%MOD)*(b%MOD))%MOD;}
inline int epow(int n, int us){int cvp = 1; while(us){if (us%2){cvp *= n;}n *= n; us /= 2;} return cvp;}
 
struct node{int l, r, val;};

int n, q, ptr;
int a[N], root[N];
node sgt[32*N];

int update(int index, int tl, int tr, int pos){

    sgt[++ptr] = sgt[index];
    index = ptr;

    if (tl == tr) sgt[index].val++;

    else {

        if (pos <= tm) sgt[index].l = update(sgt[index].l, tl, tm, pos);
        else sgt[index].r = update(sgt[index].r, tm+1, tr, pos);

        sgt[index].val = sgt[sgt[index].l].val + sgt[sgt[index].r].val;

    }

    return index;
}

 
inline int query(int v, int u, int tl, int tr, int l, int r) {
    if (tr < l || tl > r) return 0;
    if (l <= tl && tr <= r) return sgt[v].val - sgt[u].val;
    return query(sgt[v].l, sgt[u].l, tl, tm, l, r) + query(sgt[v].r, sgt[u].r, tm+1, tr, l, r);
}
 
inline int solve() {
 
    cin >> n >> q;
 
    FOR(i,1,n) cin >> a[i];

    root[0] = 0;
 
    FOR(i,1,n) root[i] = update(root[i-1], 1, 2e5, a[i]);
 
    while (q--) {

        int l, r;
        cin >> l >> r;

        int low = 1;
        int high = r-l+1;
        int h = 0;

        while (low <= high){

            int mid = low+(high-low)/2;

            int cnt = query(root[r], root[l-1], 1, 2e5, mid, 2e5);

            if (cnt >= mid) {low = mid+1; h = mid;}
            else high = mid-1;

        }

        cout << h << endl;
 
    }
 
    return 0;
}
 
int32_t main() {
 
    #ifdef LOCAL
        auto start = now;
    #endif
 
    fast;
    int t = 1;
    //cin >> t;
 
    while(t--){
        solve();
    }
 
    #ifdef LOCAL
        auto end = now;
        chrono::duration<double> elapsed = end - start;
        cout << endl << "runtime: " << endl << elapsed.count() << endl;
    #endif
 
    return 0;
}

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