제출 #1047130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1047130		vjudge1	Index (COCI21_index)	C++17	110 / 110	2356 ms	47224 KiB

index

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int n, q, a, b, minans, maxans, midans;
vector<vector<int>> tree;


void addtotree(int x, int val, int node, int nodel, int noder){
    if (x < nodel || noder <= x) return;
    if (nodel <= x && x < noder) tree[node].push_back(val);
    if (noder - nodel == 1) return;
    addtotree(x, val, 2 * node + 1, nodel, (nodel + noder) / 2);
    addtotree(x, val, 2 * node + 2, (nodel + noder) / 2, noder);
}


int greatercount(int l, int r, int val, int node, int nodel, int noder){
    if (r <= nodel || noder <= l || tree[node][tree[node].size() - 1] < val) return 0;
    if (l <= nodel && noder <= r){
        int mini = 0, maxi = noder - nodel - 1, midi;
        while (mini != maxi){
            midi = (mini + maxi) / 2;
            if (val <= tree[node][midi]) maxi = midi;
            else mini = midi + 1;
        }
        return noder - nodel - mini;
    }
    return greatercount(l, r, val, 2 * node + 1, nodel, (nodel + noder) / 2) + greatercount(l, r, val, 2 * node + 2, (nodel + noder) / 2, noder);
}


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n >> q;
    tree.resize(4 * n);
    for (int i = 0; i < n; i++){
        cin >> a;
        addtotree(i, a, 0, 0, n);
    }
    for (int i = 0; i < 4 * n; i++) sort(tree[i].begin(), tree[i].end());
    while (q--){
        cin >> a >> b;
        minans = 1;
        maxans = n;
        while (minans != maxans){
            midans = (minans + maxans + 1) / 2;
            if (midans <= greatercount(a - 1, b, midans, 0, 0, n)) minans = midans;
            else maxans = midans - 1;
        }
        cout << minans << '\n';
    }
}

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