Kyselyt

input/code.cpp: In function 'int main()':
input/code.cpp:32:24: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         if (s.count(u) >= sq) s1.insert(u);
      |                        ^

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

#define f first
#define s second

int t[202020][500];
int x[202020];
int rev_map1[500];
map<int, int> m;
vector<int> r[1000];
int rev_map[1000];
int qa[202020], qb[202020];
map<pair<int, int>, int> ans;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int sq = 1;
    while (sq*sq < n) sq++;
    multiset<int> s;
    for (int i=1; i<=n; ++i){
        cin >> x[i];
        s.insert(x[i]);
    }
    set<int> s1;
    for (auto u:s){
        if (s.count(u) >= sq) s1.insert(u);
    }
    int c =1;
    for (auto u:s1){
        m[u] = c;
        rev_map1[c]= u;
        c++;
    }
    for (int i=1; i<=n; ++i){
        int d = m[x[i]];
        for (int j=1; j<=c; ++j){
            t[i][j] = t[i-1][j];
            if (d == j) t[i][j]++;
        }
    }
    vector<pair<int, int>> v;
    for (int i=1; i<=q; ++i){
        cin >> qa[i] >> qb[i];
        if (qb[i] - qa[i] <= sq) v.push_back({qb[i], qa[i]});
    }
    sort(v.begin(), v.end());
    int ind_v = 0;
    for (int i=1; i<=sq; ++i){
        map<int, int> m1;
        int ind_s = (i-1)*sq + 1;
        int ind_e = min((i+1)*sq, n);
        int d = 1;
        
        for (int j=ind_s; j<=ind_e; ++j){
            int x1 = x[j];
            if (!m1[x1]){
                m1[x1] = d;
                rev_map[d] = x1;
                d++;
            }
            int ma = m1[x1];
            r[ma].push_back(j);
        }
        while (v[ind_v].f <= ind_e){
            bool found = false;
            for (int j=1; j<d; ++j){
                int s = 0;
                for (auto u:r[j]){
                    if (u >= v[ind_v].s && u <= v[ind_v].f) s++;
                }
                //cout << i << " " << ind_v << " " << s << " " << j << "  " << v[ind_v].f << " " << v[ind_v].s << "\n";
                if (2*s > v[ind_v].f - v[ind_v].s +1){
                    ans[{v[ind_v].s, v[ind_v].f}] = rev_map[j];
                    found = true;
                    //cout << "here " << ans[{v[ind_v].s, v[ind_v].f}] << "\n";
                    break;
                }
            }
            if (found == false) ans[{v[ind_v].f, v[ind_v].s}] = -1;
            ind_v++;
        }
        for (int j=1; j<=d; ++j) {
            r[j].clear();
            rev_map[j] = 0;
        }
    }
    
    for (int i=1; i<=q; ++i){
        int a = qa[i], b = qb[i];
        if (b-a <= sq){
            if (ans[{a,b}]) cout << ans[{a, b}] << "\n";
            else cout << "-1\n";
        }
        else {
            bool found = false;
            for (int j=1; j<=c; ++j){
                if ((t[b][j] - t[a-1][j])*2 > b-a+1 ){
                    cout << rev_map1[j] << "\n";
                    found = true;
                    break;
                }
            }
            if (found == false) cout << "-1\n";
        }
    }
}
 
 
 

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

Test 4

Group: 2, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 2, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 2, 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3, 4

Verdict: ACCEPTED

Test 8

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 4

Verdict: ACCEPTED

Test 11

Group: 3, 4

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3, 4

Verdict: RUNTIME ERROR

Test 14

Group: 4

Verdict: RUNTIME ERROR

Test 15

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 4

Verdict: TIME LIMIT EXCEEDED