/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Wrong Answer 2ms 532.0 KiB
#3 Wrong Answer 45ms 840.0 KiB

Code

#include <bits/stdc++.h>
#define int long long
#define sqrtl(x) sqrt(x)
using namespace std;

class Segmentree {
private:
  int n; vector<pair<int, int>> tree;

  void build(const vector<int>& nums, int v, int s, int e) {
    if (s == e) {
      tree[v] = {nums[s], nums[s]};
      return;
    }
    int m = (s + e) >> 1;
    build(nums, v * 2, s, m);
    build(nums, v * 2 + 1, m + 1, e);
    int prod = (tree[v * 2].first * tree[v * 2 + 1].first);
    int gcd = __gcd(tree[v * 2].second, tree[v * 2 + 1].second);
    tree[v] = {prod, gcd};
  }

  pair<int, int> query(int v, int s, int e, int l, int r) {
    if (l > r) return {1, 0};
    if (l == s && r == e) return tree[v];
    int m = (s + e) >> 1;
    auto left = query(v * 2, s, m, l, min(r, m));
    auto right = query(v * 2 + 1, m + 1, e, max(l, m + 1), r);
    int prod = (left.first * right.first);
    int gcd = __gcd(left.second, right.second);
    return {prod, gcd};
  }

public:
  Segmentree(const vector<int>& nums) {
    n = nums.size();
    if (n > 0) {
    int h = ceil(log2(n));
    int size = 2 * (1 << h) - 1;
    tree.resize(size);
    build(nums, 1, 0, n - 1);
    }
  }

  pair<int, int> query(int l, int r) {
    return query(1, 0, n - 1, l, r);
  }
};

namespace solve {
  namespace test_case {
    void main() {
      int n, x; cin >> n >> x;
      vector<int> a(n);
      for (auto& i : a) cin >> i;
      Segmentree seg(a);
      int q; cin >> q;
      while (q--) {
        int l, r;  cin >> l >> r;
        l--; r--;
        auto result = seg.query(l, r);
        if (result.first % x == 0) {
          cout << "Yes\n";
        } else {
          cout << "No\n";
        }
      }
    }
 }

 void main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t (1); cin >> t; 
    while (t--) {
      test_case::main();
    }
  }
}

signed main() { solve::main(); }

Information

Submit By
Type
Submission
Problem
P1128 Roy and Product
Contest
Brain Booster #7
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 16:37:05
Judged At
2024-11-05 16:37:05
Judged By
Score
1
Total Time
45ms
Peak Memory
840.0 KiB