結果
問題 | No.1349 Subset Product Queries |
ユーザー |
![]() |
提出日時 | 2021-09-03 23:33:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 255 ms / 2,000 ms |
コード長 | 1,659 bytes |
コンパイル時間 | 1,802 ms |
コンパイル使用メモリ | 172,732 KB |
実行使用メモリ | 96,000 KB |
最終ジャッジ日時 | 2024-12-15 18:35:38 |
合計ジャッジ時間 | 8,194 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>//#include <atcoder/all>//using namespace atcoder;#pragma GCC target ("avx2")#pragma GCC optimization ("O3")#pragma GCC optimization ("unroll-loops")using namespace std;typedef vector<int> VI;typedef vector<VI> VVI;typedef vector<string> VS;typedef pair<int, int> PII;typedef pair<int, int> pii;typedef pair<long long, long long> PLL;typedef pair<int, PII> TIII;typedef long long ll;typedef long double ld;typedef unsigned long long ull;#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)#define REP(i, n) FOR(i, 0, n)#define rep(i, a, b) for (int i = a; i < (b); ++i)#define trav(a, x) for (auto &a : x)#define all(x) x.begin(), x.end()#define MOD 1000000007template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}const double EPS = 1e-8, PI = acos(-1);const double pi = 3.141592653589793238462643383279;//ここから編集int main() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(12);int n, q, p; cin >> n >> q >> p;vector<int> a(n);REP(i,n) cin >> a[i];vector<vector<int>> dp(n+1, vector<int>(p, -1));for(int i=0; i<n; i++) {for(int j=0; j<p; j++) {dp[i+1][j] = max(dp[i+1][j], dp[i][j]);dp[i+1][(j*a[i])%p] = max(dp[i+1][(j*a[i])%p], dp[i][j]);}dp[i+1][a[i]] = i;}REP(i,q) {int l, r, k; cin >> l >> r >> k;if(dp[r][k] >= l-1) {cout << "Yes" << '\n';}else{cout << "No" << '\n';}}return 0;}