/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 328.0 KiB
#2 Accepted 2ms 328.0 KiB
#3 Time Exceeded ≥2549ms ≥6.52 MiB
#4 Accepted 2ms 560.0 KiB
#5 Accepted 2ms 444.0 KiB
#6 Time Exceeded ≥2500ms ≥6.609 MiB

Code

#define _GLIBCXX_FILESYSTEM
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

gp_hash_table<int, int, custom_hash> mp;

const int N = 2e5+2, B = 125;
int a[N];
set<pair<int,int>,greater<pair<int,int>>> st;
void remove(int idx) {
    if(st.find({mp[a[idx]],a[idx]}) != st.end()) st.erase({mp[a[idx]],a[idx]});
    mp[a[idx]]--;
    if(mp[a[idx]]) st.insert({mp[a[idx]],a[idx]});
}
void add(int idx) {
    if(st.find({mp[a[idx]],a[idx]}) != st.end()) st.erase({mp[a[idx]],a[idx]});
    mp[a[idx]]++;
    st.insert({mp[a[idx]],a[idx]});
}
int get_answer(int l) {
    if(st.empty()) return -1;
    auto it = st.begin();
    int ans = INT_MAX;
    if((*it).first > l) ans = min(ans, (*it).second);
    st.erase(st.begin());
    if(st.size()) {
        auto it1 = st.begin();
        if((*it1).first > l) ans = min(ans, (*it1).second);
    }
    st.insert({(*it).first,(*it).second});
    if(ans == INT_MAX) return -1;
    return ans;
}


struct Query {
  int l, r, idx;
  bool operator < (const Query &x) const {
    if(l / B == x.l / B) return ((l / B) & 1) ? r > x.r : r < x.r;
    return l / B < x.l / B;
  }
};

vector<int> mo_s_algorithm(vector<Query> queries) {
    vector<int> answers(queries.size());
    sort(queries.begin(), queries.end());

    int cur_l = 0;
    int cur_r = -1;
    for (Query q : queries) {
        while (cur_l > q.l) {
            cur_l--;
            add(cur_l);
        }
        while (cur_r < q.r) {
            cur_r++;
            add(cur_r);
        }
        while (cur_l < q.l) {
            remove(cur_l);
            cur_l++;
        }
        while (cur_r > q.r) {
            remove(cur_r);
            cur_r--;
        }
        answers[q.idx] = get_answer((q.r - q.l + 1) / 3);
    }
    return answers;
}

void solve() {
    int n,q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<Query> query(q);
    for(int i = 0; i < q; i++) {
        cin >> query[i].l >> query[i].r;
        query[i].idx = i;
    }
    vector<int> ans = mo_s_algorithm(query);
    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    // cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    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 16:00:23
Judged At
2024-11-11 02:28:55
Judged By
Score
20
Total Time
≥2549ms
Peak Memory
≥6.609 MiB