Submission #1318033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318033		WH8	Index (COCI21_index)	C++17	110 / 110	337 ms	19324 KiB

index

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

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n=0): n(n), bit(n+1,0) {}
    void reset() { fill(bit.begin(), bit.end(), 0); }
    void add(int i, int v){
        for(; i<=n; i+=i&-i) bit[i]+=v;
    }
    int sumPrefix(int i) const{
        int s=0;
        for(; i>0; i-=i&-i) s+=bit[i];
        return s;
    }
    int sumRange(int l,int r) const{
        if(l>r) return 0;
        return sumPrefix(r)-sumPrefix(l-1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,q;
    cin >> n >> q;
    vector<int> v(n+1);
    vector<pair<int,int>> papers; papers.reserve(n);
    for(int i=1;i<=n;i++){
        cin >> v[i];
        papers.push_back({v[i], i});
    }
    sort(papers.begin(), papers.end(), [&](auto &a, auto &b){
        return a.first > b.first; // descending by value
    });

    vector<int> L(q), R(q);
    for(int i=0;i<q;i++){
        cin >> L[i] >> R[i];
        if(L[i] > R[i]) swap(L[i], R[i]);
    }

    // h is in [0..len], so search on [0..len+1) => lo inclusive, hi exclusive
    vector<int> lo(q, 0), hi(q);
    for(int i=0;i<q;i++){
        int len = R[i]-L[i]+1;
        hi[i] = len + 1;
    }

    Fenwick fw(n);

    // buckets: mid -> list of queries
    vector<vector<int>> bucket(n+2);
    bool changed = true;

    while(changed){
        changed = false;
        for(int m=0;m<=n+1;m++) bucket[m].clear();

        int active = 0;
        for(int i=0;i<q;i++){
            if(hi[i] - lo[i] > 1){
                int mid = (lo[i] + hi[i]) >> 1;
                bucket[mid].push_back(i);
                active++;
            }
        }
        if(active == 0) break;

        fw.reset();
        int pptr = 0; // pointer into papers (descending by value)

        // process mids from high to low so we only sweep papers once
        for(int mid=n+1; mid>=1; mid--){
            // activate all positions with value >= mid
            while(pptr < n && papers[pptr].first >= mid){
                fw.add(papers[pptr].second, 1);
                pptr++;
            }
            // answer all queries with this mid
            for(int qi : bucket[mid]){
                int cnt = fw.sumRange(L[qi], R[qi]); // #papers with citations >= mid
                if(cnt >= mid) lo[qi] = mid;
                else hi[qi] = mid;
                changed = true;
            }
        }
    }

    for(int i=0;i<q;i++){
        cout << lo[i] << "\n";
    }
    return 0;
}

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