fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define file "a"
  4. // #define int long long   
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define pii pair<int, int>
  9. #define pb push_back
  10. #define pf push_front
  11. #define sz(a) (int)a.size()
  12. #define mask(i) (1 << (int)(i))
  13. const int N = 2e5, mod = 1e9 + 7, inf = 1e9, K = __lg(N);
  14. void add(int &a, int b) { a += b; if (a >= mod) a -= mod; }
  15. void MIN(int &a, int b) { a = min(a, b); }
  16. int n, q;
  17. int mx[N + 2][K + 2], lg[N + 2], mn[N + 2][K + 2], g[N + 2][K + 2];
  18. int getmax(int l, int r)
  19. {
  20.   int k = lg[r - l + 1];
  21.   return max(mx[l][k], mx[r - mask(k) + 1][k]);
  22. }
  23. int getmin(int l, int r)
  24. {
  25.   int k = lg[r - l + 1];
  26.   return min(mn[l][k], mn[r - mask(k) + 1][k]);
  27. }
  28. int getgcd(int l, int r)
  29. {
  30.   int k = lg[r - l + 1];
  31.   return __gcd(g[l][k], g[r - mask(k) + 1][k]);
  32. }
  33. signed main() 
  34. {
  35.   ios_base::sync_with_stdio(0);
  36.   cin.tie(0); cout.tie(0);
  37.   if (fopen(file".inp", "r")) 
  38.   {
  39.     freopen(file".inp", "r", stdin);
  40.     freopen(file".out", "w", stdout);
  41.   }
  42.   cin >> n >> q;
  43.   for (int i = 1; i <= n; i++) 
  44.     cin >> mx[i][0], mn[i][0] = g[i][0] = mx[i][0];
  45.   lg[1] = 0;
  46.   for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
  47.   for (int j = 1; j <= lg[n]; j++) 
  48.   for (int i = 1; i + mask(j) - 1 <= n; i++)
  49.   {
  50.     mx[i][j] = max(mx[i][j - 1], mx[i + mask(j - 1)][j - 1]);
  51.     mn[i][j] = min(mn[i][j - 1], mn[i + mask(j - 1)][j - 1]);
  52.     g[i][j] = __gcd(g[i][j - 1], g[i + mask(j - 1)][j - 1]);
  53.   }
  54.   while (q--)
  55.   {
  56.     int l, r;
  57.     cin >> l >> r;
  58.     cout << getmax(l, r) << " " << getmin(l, r) << "\n";
  59.   }
  60. }
Success #stdin #stdout 0s 7640KB
comments (?)
stdin
copy 
1
stdout
copy 
Standard output is empty
https://ideone.com/YaTZKA
language:
C++14 (gcc 8.3)
created:
1 day 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!