fork download
copy 
  1. // Author: __BruteForce__
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define MAX_N 100005
  7.  
  8. int n, q;
  9. int a[MAX_N];
  10. vector<int> val[MAX_N];
  11. int lo[MAX_N], hi[MAX_N], ql[MAX_N], qr[MAX_N];
  12. stack<int> to_check[MAX_N];
  13. int bit[MAX_N];
  14.  
  15. void update(int p) {
  16.     for (; p <= n; p += p & -p) bit[p]++;
  17. }
  18.  
  19. int get(int p) {
  20.     int sum = 0;
  21.     for (; p; p -= p & -p) sum += bit[p];
  22.     return sum;
  23. }
  24.  
  25. int main() {
  26.     cin.tie(0)->sync_with_stdio(false);
  27.  
  28.     cin >> n >> q;
  29.     for (int i = 1; i <= n; i++) {
  30.         cin >> a[i];
  31.         val[a[i]].push_back(i);
  32.     }
  33.     for (int i = 1; i <= q; i++) {
  34.         cin >> ql[i] >> qr[i];
  35.         lo[i] = 1, hi[i] = MAX_N - 1;
  36.     }
  37.  
  38.     bool changed = true;
  39.     while (changed) {
  40.         // Reset
  41.         changed = false;
  42.         memset(bit, 0, sizeof(bit));
  43.         for (int i = 1; i <= q; i++)
  44.             if (lo[i] != hi[i]) to_check[(lo[i] + hi[i]) >> 1].push(i);
  45.  
  46.         for (int mid = 1; mid < MAX_N; mid++) {
  47.             for (int pos : val[mid]) update(pos);
  48.  
  49.             while (to_check[mid].size()) {
  50.                 changed = true;
  51.                 int idx = to_check[mid].top();
  52.                 to_check[mid].pop();
  53.  
  54.                 int cnt = get(qr[idx]) - get(ql[idx] - 1);
  55.                 int range = qr[idx] - ql[idx] + 1;
  56.                 if (cnt >= (range + 1) / 2)
  57.                     hi[idx] = mid;
  58.                 else
  59.                     lo[idx] = mid + 1;
  60.             }
  61.         }
  62.     }
  63.  
  64.     for (int i = 1; i <= q; i++) cout << lo[i] << "\n";
  65. }
  66.  
Success #stdin #stdout 0.04s 75040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/51txVx
language:
C++14 (gcc 8.3)
created:
1 year 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!