Submission #387138

#	Time	Username	Problem	Language	Result	Execution time	Memory
387138		phathnv	Index (COCI21_index)	C++11	110 / 110	2457 ms	134496 KiB

index

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

typedef long long ll;

const int N = 2e5 + 7;

struct Node{
    int sum;
    Node *leftChild, *rightChild;
    Node(int _x){
        sum = _x;
        leftChild = rightChild = nullptr;
    }
};

Node* Build(int l, int r){
    Node *res = new Node(0);
    if (l == r)
        return res;
    int mid = (l + r) >> 1;
    res->leftChild = Build(l, mid);
    res->rightChild = Build(mid + 1, r);
    res->sum = res->leftChild->sum + res->rightChild->sum;
    return res;
}

Node* Update(Node *cur, int l, int r, int pos){
    if (pos < l || r < pos)
        return cur;
    Node *res = new Node(1);
    if (l == r)
        return res;
    int mid = (l + r) >> 1;
    res->leftChild = Update(cur->leftChild, l, mid, pos);
    res->rightChild = Update(cur->rightChild, mid + 1, r, pos);
    res->sum = res->leftChild->sum + res->rightChild->sum;
    return res;
}

int Get(Node *cur, int l, int r, int u, int v){
    if (v < l || r < u)
        return 0;
    if (u <= l && r <= v)
        return cur->sum;
    int mid = (l + r) >> 1;
    return Get(cur->leftChild, l, mid, u, v) + Get(cur->rightChild, mid + 1, r, u, v);
}

int n, q, p[N], ind[N];
Node *ver[N], *root;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    root = Build(1, n);
    sort(ind + 1, ind + 1 + n, [&](const int &x, const int &y){
            return p[x] > p[y];
         });
    int ptr = 1;
    for(int i = n; i >= 1; i--){
        while (ptr <= n && p[ind[ptr]] >= i)
            root = Update(root, 1, n, ind[ptr++]);
        ver[i] = root;
    }

    while (q--){
        int l, r, lo = 2, hi = n, res = 1;
        cin >> l >> r;
        while (lo <= hi){
            int mid = (lo + hi) >> 1;
            if (Get(ver[mid], 1, n, l, r) >= mid){
                res = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        cout << res << '\n';
    }

    return 0;
}

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