fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <stdio.h>
  4. #include <set>
  5. #include <vector>
  6. #include <map>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <memory.h>
  10. #include <string>
  11. #include <sstream>
  12. #include <cstdlib>
  13. #include <ctime>
  14. #include <cassert>
  15.  
  16. using namespace std;
  17.  
  18. typedef long long LL;
  19. typedef pair<int,int> PII;
  20.  
  21. #define MP make_pair
  22. #define PB push_back
  23. #define FF first
  24. #define SS second
  25.  
  26. #define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
  27. #define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
  28. #define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
  29.  
  30. #define MOD 1000000007
  31. #define INF 2000000000
  32.  
  33. int candF[4], candS[4];
  34.  
  35. vector<PII> data; vector< vector<int> > common; int csz;
  36.  
  37. const int MAXN = 200010;
  38. int f[MAXN];
  39.  
  40. int N, M, Q;
  41.  
  42. int main() {
  43.     scanf("%d%d", &N, &M);
  44.  
  45.     for (int i = 1; i <= N; i++) {
  46.         scanf("%d", &f[i]); data.PB(MP(f[i], i));
  47.     }
  48.  
  49.     data.PB(MP(N+1,N+1));
  50.  
  51.     sort(data.begin(), data.end());
  52.  
  53.     int diffidx = -1;
  54.  
  55.     for (int i = 0; i < data.size(); i++) {
  56.         if (i > 0 && data[i].FF != data[i-1].FF) {
  57.             int cnt = i-1 - diffidx;
  58.  
  59.             if (cnt >= 500) {
  60.                 common.PB(vector<int>());
  61.                 for (int j = diffidx + 1; j < i; j++) common[csz].PB(data[j].SS);
  62.                 csz++;
  63.             }
  64.  
  65.             diffidx = i-1;
  66.         }
  67.     }
  68.  
  69.     scanf("%d", &Q); int l, r;
  70.  
  71.     for (int i = 0; i < Q; i++) {
  72.         scanf("%d%d", &l, &r); int qlen = r - l + 1;
  73.  
  74.         if (qlen >= 1500) {
  75.             int good = 0; bool found = false;
  76.  
  77.             for (int j = 0; j < csz; j++) {
  78.                 int cnt = upper_bound(common[j].begin(), common[j].end(), r) - lower_bound(common[j].begin(), common[j].end(), l);
  79.  
  80.                 good += (3 * cnt >= 2 * qlen) + (3 * cnt >= qlen);
  81.                 if (good >= 2) { found = true; break; }
  82.             }
  83.  
  84.             if (found) printf("YES\n");
  85.             else printf("NO\n");
  86.         }
  87.         else {
  88.             int candsz = 0; vector<PII> cand;
  89.  
  90.             for (int j = l; j <= r; j++) {
  91.                 bool inserted = false;
  92.  
  93.                 for (int k = 0; k < cand.size(); k++) {
  94.                     if (cand[k].SS == f[j]) {
  95.                         cand[k].FF += 1;
  96.                         inserted = true;
  97.                     }
  98.                 }
  99.  
  100.                 if (!inserted) cand.PB(MP(1, f[j]));
  101.  
  102.                 sort(cand.rbegin(), cand.rend());
  103.  
  104.                 if (cand.size() == 4) {
  105.                     for (int k = 0; k < cand.size(); k++) cand[k].FF -= 1;
  106.                     while (cand[cand.size()-1].FF == 0) cand.pop_back();
  107.                 }
  108.             }
  109.  
  110.             vector<int> candcnt(cand.size());
  111.  
  112.             for (int j = l; j <= r; j++) {
  113.                 for (int k = 0; k < cand.size(); k++) {
  114.                     if (f[j] == cand[k].SS) candcnt[k]++;
  115.                 }
  116.             }
  117.  
  118.             int good = 0;
  119.  
  120.             for (int k = 0; k < cand.size(); k++) {
  121.                 good += (3 * candcnt[k] >= 2 * qlen) + (3 * candcnt[k] >= qlen);
  122.             }
  123.  
  124.             if (good >= 2) printf("YES\n");
  125.             else printf("NO\n");
  126.         }
  127.     }
  128.  
  129.     return 0;
  130. }
  131.  
Success #stdin #stdout 0s 4016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HyDo11
language:
C++ (gcc 8.3)
created:
8 years 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!