fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define vi vector<int>
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define ii pair<int , int>
  9. #define pq priority_queue
  10. #define iii pair<int , pair<int , int>>
  11. #define fo(i,l,r) for(int i=l;i<=r;i++)
  12. #define fod(i,r,l) for(int i=r;i>=l;i--)
  13. #define fill(f,x) memset(f,x,sizeof(f))
  14. #define NAME "file"
  15.  
  16. const int N = 3e5 + 5, mod = 1e9 + 7;
  17. int n , q , a[N] , bit[N] , l[N] , r[N] , k[N] , L[N] , R[N] , ans[N] , val[N];
  18. vector <int> dat[N] , qr[N];
  19.  
  20. struct time
  21. {
  22.     int l , r , x;
  23. } td[N];
  24.  
  25.  
  26. void upd(int x, int v) 
  27. {
  28. 	for (; x <= n; x += x & -x) bit[x] += v;
  29. }
  30.  
  31. int get(int x) 
  32. {
  33. 	int res = 0;
  34. 	for (; x >= 1; x &= x - 1) res += bit[x];
  35. 	return res;
  36. }
  37.  
  38.  
  39.  
  40. signed main()
  41. {
  42.     ios_base::sync_with_stdio(0);
  43.     cin.tie(0);  cout.tie(0);
  44.     //freopen(NAME".INP" , "r" , stdin);
  45.     //freopen(NAME".OUT" , "w" , stdout);
  46.  
  47.     cin >> n >> q;
  48.     map <int , int> mp;
  49.     fo(i, 1, n)
  50.     {
  51.         cin >> a[i];
  52.         mp[a[i]] = 1;
  53.     }
  54.     int ord = 0;
  55.     for (auto e : mp)
  56.     {
  57.         ord++;
  58.         val[ord] = e.fi;
  59.         mp[e.fi] = ord;
  60.     }
  61.     fo(i, 1, n)
  62.     {
  63.         a[i] = mp[a[i]];
  64.         dat[a[i]].push_back(i);
  65.     }
  66.  
  67.     fo(i, 1, q)
  68.         cin >> l[i] >> r[i] >> k[i];
  69.  
  70.     //
  71.  
  72.     fo(i, 1, q)
  73.     {
  74.         L[i] = 1;
  75.         R[i] = ord;
  76.         ans[i] = -1;
  77.     }
  78.  
  79.     bool run = 1;
  80.     while (run)
  81.     {
  82.         run = 0;
  83.  
  84.         fo(i, 1, q)
  85.         if (L[i] <= R[i])
  86.         {
  87.             run = 1;
  88.             qr[(L[i] + R[i]) / 2].push_back(i);
  89.         }
  90.  
  91.         fo(x, 1, ord)
  92.         {
  93.             for (auto pos : dat[x])
  94.                 upd(pos , 1);
  95.  
  96.             for (auto i : qr[x])
  97.             {
  98.                 if (get(r[i]) - get(l[i] - 1) >= k[i])
  99.                 {
  100.                     ans[i] = val[x];
  101.                     R[i] = x - 1;
  102.                 }  
  103.                 else
  104.                     L[i] = x + 1;
  105.             }
  106.         }
  107.  
  108.         fo(i, 1, n) bit[i] = 0;
  109.         fo(i, 1, ord) qr[i].clear();
  110.     }
  111.  
  112.     fo(i, 1, q)
  113.         cout << ans[i] << '\n';
  114. }
  115. // haronnee_
Success #stdin #stdout 0.01s 20040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UkIJs9
language:
C++ (gcc 8.3)
created:
1 hour 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!