/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 16ms 18.77 MiB
#2 Accepted 16ms 18.793 MiB
#3 Accepted 780ms 32.062 MiB
#4 Accepted 15ms 18.77 MiB
#5 Accepted 16ms 18.734 MiB
#6 Wrong Answer 1265ms 32.266 MiB
#7 Accepted 499ms 32.238 MiB
#8 Accepted 824ms 32.43 MiB
#9 Accepted 1899ms 32.41 MiB
#10 Accepted 2013ms 32.395 MiB
#11 Accepted 1518ms 32.434 MiB
#12 Accepted 1630ms 32.191 MiB
#13 Accepted 771ms 32.133 MiB
#14 Accepted 1669ms 32.387 MiB
#15 Accepted 1844ms 32.441 MiB
#16 Accepted 1954ms 32.227 MiB

Code

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define int long long
#define endl '\n'

using namespace std;
using pii = pair<int, int>;
using tup = tuple<int, int, int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// template <class T> using ordered_set = tree<T, null_type,
//                          less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int inf = 1e9;
const int mod = 1000000007;
const double eps = 1e-9;
const int N = 200005;

void preprocess() {}

struct Node {
    vector<pii> v;

    Node() {}
    Node(int val) { v = {{1, val}}; }
};

Node merge(Node &a, Node &b) {
    map<int, int> mp;
    for(auto [y, x] : a.v) mp[x] = y;
    for(auto [y, x] : b.v) mp[x] += y;
    vector<pii> v;
    for(auto [x, y] : mp) v.push_back({y, x});
    sort(v.begin(), v.end(), greater<pii>());
    while(v.size() > 3) v.pop_back();
    Node res;
    res.v = v;
    return res;
}

Node tr[N * 4];
int a[N];

void build(int node, int b, int e) {
    if(b == e) {
        tr[node] = Node(a[b]);
        return;
    }
    int mid = b + e >> 1;
    build(node*2, b, mid);
    build(node*2+1, mid+1, e);

    tr[node] = merge(tr[node*2], tr[node*2+1]);
}

Node query(int node, int b, int e, int i, int j) {
    if(i > e || j < b) return Node();
    if(b >= i && e <= j) return tr[node];

    int mid = b + e >> 1;
    Node left = query(node*2, b, mid, i, j);
    Node right = query(node*2+1, mid+1, e, i, j);

    return merge(left, right);
}


void solve(int tc) {
    int n, q;
    cin >> n >> q;

    for(int i=1; i<=n; i++) cin >> a[i];
    build(1, 1, n);

    while(q--) {
        int l, r;
        cin >> l >> r;
        Node res = query(1, 1, n, l, r);
        int ans = inf;

        for(auto [y, x] : res.v) 
            if(y * 3 > r-l+1) ans = min(ans, x);
        if(ans == inf) ans = -1;

        cout << ans << endl;
    }
}   

int32_t main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cout.precision(10);

    preprocess();

    int T = 1;
    // cin >> T;

    for (int i = 1; i <= T; i++) {  
        solve(i);
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1103 The Secret Garden of Numbers
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 18:57:24
Judged At
2024-11-05 18:57:24
Judged By
Score
95
Total Time
2013ms
Peak Memory
32.441 MiB