제출 #1119427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1119427		ezzzay	Index (COCI21_index)	C++14	60 / 110	2552 ms	9608 KiB

index

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

const int MAXN = 200005;

// Structure to store query information
struct Query {
    int l, r, idx, block;
};

// Comparison function for sorting queries
bool compareQueries(const Query& a, const Query& b) {
    if (a.block != b.block) return a.block < b.block;
    return a.r < b.r;
}

class Solution {
private:
    int n, q;
    vector<int> citations;
    vector<int> answers;
    vector<int> count;

    // Calculate h-index for current range
    int calculateHIndex() {
        int total = 0;
        for (int h = n; h >= 0; h--) {
            total += count[h];
            if (total >= h) {
                return h;
            }
        }
        return 0;
    }

public:
    void solve() {
        // Input
        cin >> n >> q;
        
        // Read citations
        citations.resize(n);
        for (int i = 0; i < n; i++) {
            cin >> citations[i];
        }

        // Prepare queries
        vector<Query> queries(q);
        int blockSize = sqrt(n);
        
        for (int i = 0; i < q; i++) {
            cin >> queries[i].l >> queries[i].r;
            queries[i].l--; // Convert to 0-based indexing
            queries[i].r--;
            queries[i].idx = i;
            queries[i].block = queries[i].l / blockSize;
        }

        // Sort queries
        sort(queries.begin(), queries.end(), compareQueries);

        // Prepare data structures
        answers.resize(q);
        count.resize(n + 1, 0);

        // Initial state
        int currentL = 0, currentR = -1;

        // Process queries using MO's algorithm
        for (const Query& query : queries) {
            // Extend/shrink range to match query
            while (currentR < query.r) {
                currentR++;
                if (citations[currentR] >= n) {
                    count[n]++;
                } else {
                    count[citations[currentR]]++;
                }
            }

            while (currentR > query.r) {
                if (citations[currentR] >= n) {
                    count[n]--;
                } else {
                    count[citations[currentR]]--;
                }
                currentR--;
            }

            while (currentL > query.l) {
                currentL--;
                if (citations[currentL] >= n) {
                    count[n]++;
                } else {
                    count[citations[currentL]]++;
                }
            }

            while (currentL < query.l) {
                if (citations[currentL] >= n) {
                    count[n]--;
                } else {
                    count[citations[currentL]]--;
                }
                currentL++;
            }

            // Calculate h-index for current range
            int hIndex = 0;
            int total = 0;
            for (int h = n; h >= 0; h--) {
                total += count[h];
                if (total >= h) {
                    hIndex = h;
                    break;
                }
            }

            answers[query.idx] = hIndex;
        }

        // Output answers in original query order
        for (int ans : answers) {
            cout << ans << "\n";
        }
    }
};

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

    Solution solution;
    solution.solve();

    return 0;
}

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