fork download
copy 
  1. //// YENNHI ////
  2. #include<bits/stdc++.h>
  3. #define ll long long
  4. #define endl "\n"
  5. #define pb push_back
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int Maxn = 1e6;
  12. const int MOD = 1e9 + 7;
  13. const ll INF = 1e18;
  14.  
  15. int n,R, q, l, r, Min,x, Max;
  16. int a[Maxn + 10];
  17. int R_max[Maxn + 10];
  18. multiset<int> s;
  19.  
  20. bool check(int val) {
  21.     if(s.empty()) return true;
  22.     Min = *s.begin();
  23.     Max = *s.rbegin();
  24.     if(val % Min != 0 && Min % val != 0) return false;
  25.     if(Max % val != 0 && val % Max != 0) return false;
  26.     for(auto it = s.begin(); it != s.end(); it = s.upper_bound(*it)){
  27.         x = *it;
  28.         if(val % x != 0 && x % val != 0){
  29.             return false;
  30.         }
  31.     }
  32.     return true;
  33. }
  34.  
  35. void sub1() {
  36.     R = 1;
  37.     for (int L = 1; L <= n; L++) {
  38.         while (R <= n && check(a[R])) {
  39.             s.insert(a[R]);
  40.             R++;
  41.         }
  42.         R_max[L] = R - 1;
  43.         auto it = s.find(a[L]);
  44.         if (it != s.end()) {
  45.             s.erase(it);
  46.         }
  47.     }
  48.     while (q--) {
  49.         cin >> l >> r;
  50.         if(r <= R_max[l]) cout << "YES" << endl;
  51.         else cout << "NO" << endl;
  52.     }
  53. }
  54.  
  55. int main() {
  56.     ios_base::sync_with_stdio(false);
  57.     cin.tie(NULL);
  58.     freopen("terminal.IN", "r", stdin);
  59.     freopen("terminal.OU", "w", stdout);
  60.     cin >> n >> q;
  61.     for (int i = 1; i <= n; i++) {
  62.         cin >> a[i];
  63.     }
  64.     sub1();
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YFVDsZ
language:
C++14 (gcc 8.3)
created:
15 hours 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!