fork download
  1. /******************************************
  2. * AUTHOR: BHUVNESH JAIN *
  3. * INSTITUITION: BITS PILANI, PILANI *
  4. ******************************************/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. typedef long long LL;
  10. typedef long double LD;
  11.  
  12. const int MAX = 3e5 + 5;
  13. const int LIM = 1e5 + 5;
  14.  
  15. int a[MAX];
  16. vector<int> freq[LIM];
  17.  
  18. int main() {
  19. #ifndef ONLINE_JUDGE
  20. freopen("inp.txt", "r", stdin);
  21. #endif
  22. int n, c, q, l, r;
  23. scanf("%d %d", &n, &c);
  24. for(int i = 1; i <= n; ++i) {
  25. scanf("%d", &a[i]);
  26. freq[a[i]].push_back(i);
  27. }
  28. int pos, val, many;
  29. scanf("%d", &q);
  30. while(q--) {
  31. scanf("%d %d", &l, &r);
  32. bool result = false;
  33. for(int rep = 0; rep < 20; ++rep) {
  34. pos = l + rand() % (r - l + 1);
  35. val = a[pos];
  36. many = upper_bound(freq[val].begin(), freq[val].end(), r) - lower_bound(freq[val].begin(), freq[val].end(), l);
  37. if (2*many > (r - l + 1)) {
  38. result = true;
  39. printf("yes %d\n", val);
  40. break;
  41. }
  42. }
  43. if (!result) printf("no\n");
  44. }
  45. return 0;
  46. }
Success #stdin #stdout 0s 5816KB
stdin
10 3
1 2 1 2 1 2 3 2 3 3
8
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10
stdout
no
yes 1
no
yes 1
no
yes 2
no
yes 3