Submission #1119429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119429		ezzzay	Index (COCI21_index)	C++14	20 / 110	2582 ms	1616 KiB

index

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

const int MAXN = 2e5 + 5;

int n, q;
int citations[MAXN];
int fenwick[MAXN];

void update(int idx, int val) {
    while (idx <= n) {
        fenwick[idx] += val;
        idx += idx & -idx;
    }
}

int query(int idx) {
    int sum = 0;
    while (idx > 0) {
        sum += fenwick[idx];
        idx -= idx & -idx;
    }
    return sum;
}

int calculate_h_index(int l, int r) {
    // Create frequency array for the range
    vector<int> freq(n + 1, 0);
    for (int i = l; i <= r; i++) {
        freq[min(citations[i], n)]++;
    }
    
    // Calculate cumulative sum from end
    int total_papers = 0;
    for (int h = n; h >= 0; h--) {
        total_papers += freq[h];
        if (total_papers >= h) {
            return h;
        }
    }
    
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // Read input
    cin >> n >> q;
    
    // Read citations
    for (int i = 1; i <= n; i++) {
        cin >> citations[i];
    }
    
    // Process queries
    while (q--) {
        int l, r;
        cin >> l >> r;
        
        // Calculate and output h-index for the range
        cout << calculate_h_index(l, r) << "\n";
    }
    
    return 0;
}

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