Submission #942560

#	Time	Username	Problem	Language	Result	Execution time	Memory
942560		vjudge1	Index (COCI21_index)	C++17	60 / 110	2563 ms	65368 KiB

index

#include <bits/stdc++.h>

using namespace std;

using ld = long double;
using ll = long long;

#define int ll

#define sz(x) (int)x.size()

const int N = 2e5+5;
int n, q;
int p[N];

vector<int> T[4*N];

void init(int i, int tl, int tr){
    if(tl == tr){
        T[i].push_back(p[tl]);
        return;
    }

    int m = (tl + tr) / 2;

    init(2*i+1, tl, m);
    init(2*i+2, m+1, tr);

    merge(T[2*i+1].begin(), T[2*i+1].end(), T[2*i+2].begin(), T[2*i+2].end(), back_inserter(T[i]));

}

int query(int l, int r, int k, int i, int tl, int tr){
    if(r < tl or l > tr){
        return 0;
    }
    if(l <= tl && tr <= r){
        return lower_bound(T[i].begin(), T[i].end(), k) - T[i].begin();
    }
    int m = (tl + tr) / 2;
    return query(l, r, k, 2*i+1, tl, m) + query(l, r, k, 2*i+2, m+1, tr);
}

int query(int l, int r, int k){
    return query(l, r, k, 0, 0, n-1);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for(int i=0; i<n; ++i){
        cin >> p[i];
    }

    init(0, 0, n-1);

    while(q--){
        int l, r;
        cin >> l >> r;
        l--, r--;

        int low = 1, high = r - l + 1;
        int res = 1;
        while(low <= high){
            int mid = (low + high) / 2;

            int tmp = r - l + 1 - query(l, r, mid);

            if(tmp >= mid){
                res = mid;
                low = mid+1;
            } else {
                high = mid-1;
            }

        }

        cout << res << endl;


    }

}

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