fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXN = 3e5 + 5;
  5. mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
  6.  
  7. int rand(int l, int r) {return uniform_int_distribution<int>(l, r)(rng);}
  8.  
  9.  
  10. int n , q , S , ans;
  11. ll a[MAXN] , cnt[MAXN] , res[MAXN];
  12. int L = 1 , R = 0;
  13.  
  14. struct query{
  15.     int l , r , id , k;
  16. } qu[MAXN];
  17.  
  18. void MO(int i)
  19. {
  20.     while(L < qu[i].l){
  21.         cnt[a[L]]--;
  22.         L++;
  23.     }
  24.     while(L > qu[i].l){
  25.         L--;
  26.         cnt[a[L]]++;
  27.     }
  28.     while(R < qu[i].r){
  29.         R++;
  30.         cnt[a[R]]++;
  31.  
  32.     }
  33.     while(R > qu[i].r){
  34.         cnt[a[R]]--;
  35.         R--;
  36.     }
  37. }
  38.  
  39.  
  40. int main(){
  41.     ios::sync_with_stdio(0);
  42.     cin.tie(0);
  43.     cin >> n >> q;
  44.     S = sqrt(n);
  45.     for(int i = 1 ; i <= n ; i++) cin >> a[i];
  46.  
  47.     for(int i = 1 ; i <= q ; i++){
  48.         cin >> qu[i].l >> qu[i].r >> qu[i].k;
  49.         qu[i].id = i;
  50.     }
  51.     sort(qu + 1 , qu + 1 + q , [&] (query x, query y){
  52.         if (x.l / S == y.l) return x.r < y.r;
  53.         return x.l < y.l;
  54.     });
  55.  
  56.     for(int i = 1 ; i <= q ; i++){
  57.         MO(i);
  58.         ll ans = 1e18;
  59.         for(int j = 1 ; j <= 100 ; j++){
  60.  
  61.             int id = rand(qu[i].l , qu[i].r);
  62.  
  63.             if(cnt[a[id]] > (qu[i].r - qu[i].l + 1) / qu[i].k)
  64.                 ans = min(ans , a[id]);
  65.         }
  66.         res[qu[i].id] = ans;
  67.     }
  68.     for(int i = 1 ; i <= q ; i++)
  69.         cout << ((res[i] == 1e18) ? -1 : res[i]) << endl;
  70. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/M71mFw
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!