/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 536.0 KiB
#3 Time Exceeded ≥2599ms ≥5.047 MiB
#4 Accepted 1ms 532.0 KiB
#5 Accepted 1ms 320.0 KiB
#6 Time Exceeded ≥2599ms ≥4.973 MiB

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>

using namespace std;

struct Query {
    int l, r, idx;
};

bool compare(const Query& a, const Query& b) {
    int block_size = 1000;
    if (a.l / block_size != b.l / block_size) {
        return a.l < b.l;
    }
    return a.r < b.r;
}

vector<int> moAlgorithm(int n, int q, const vector<int>& a, const vector<Query>& queries) {
    vector<int> res(q);
    vector<int> freq(n + 1, 0);
    int currentL = 0, currentR = 0;
    
    for (int i = 0; i < q; ++i) {
        int l = queries[i].l - 1; 
        int r = queries[i].r - 1; 
        
        while (currentR <= r) {
            freq[a[currentR]]++;
            currentR++;
        }
        while (currentR > r + 1) {
            currentR--;
            freq[a[currentR]]--;
        }
        
        while (currentL < l) {
            freq[a[currentL]]--;
            currentL++;
        }
        while (currentL > l) {
            currentL--;
            freq[a[currentL]]++;
        }

        int threshold = (r - l + 1) / 3;
        int minX = numeric_limits<int>::max();

        for (int j = 1; j <= n; ++j) {
            if (freq[j] > threshold) {
                minX = min(minX, j);
            }
        }

        res[queries[i].idx] = (minX == numeric_limits<int>::max()) ? -1 : minX;
    }

    return res;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<Query> queries(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].idx = i; 
    }

    sort(queries.begin(), queries.end(), compare);

    vector<int> res = moAlgorithm(n, q, a, queries);

    for (int r : res) {
        cout << r << endl;
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1103 The Secret Garden of Numbers
Contest
Brain Booster #7
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 15:03:11
Judged At
2024-11-05 15:03:11
Judged By
Score
20
Total Time
≥2599ms
Peak Memory
≥5.047 MiB