結果
問題 | No.1349 Subset Product Queries |
ユーザー | HIR180 |
提出日時 | 2021-01-16 13:06:44 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 659 ms / 2,000 ms |
コード長 | 2,334 bytes |
コンパイル時間 | 3,315 ms |
コンパイル使用メモリ | 235,740 KB |
実行使用メモリ | 101,404 KB |
最終ジャッジ日時 | 2023-08-18 09:12:40 |
合計ジャッジ時間 | 19,213 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 30 ms
101,176 KB |
testcase_01 | AC | 30 ms
101,232 KB |
testcase_02 | AC | 30 ms
101,272 KB |
testcase_03 | AC | 30 ms
101,228 KB |
testcase_04 | AC | 31 ms
101,404 KB |
testcase_05 | AC | 30 ms
101,232 KB |
testcase_06 | AC | 30 ms
101,192 KB |
testcase_07 | AC | 30 ms
101,296 KB |
testcase_08 | AC | 30 ms
101,224 KB |
testcase_09 | AC | 31 ms
101,364 KB |
testcase_10 | AC | 30 ms
101,264 KB |
testcase_11 | AC | 653 ms
101,280 KB |
testcase_12 | AC | 630 ms
101,180 KB |
testcase_13 | AC | 619 ms
101,240 KB |
testcase_14 | AC | 593 ms
101,204 KB |
testcase_15 | AC | 640 ms
101,252 KB |
testcase_16 | AC | 659 ms
101,244 KB |
testcase_17 | AC | 528 ms
101,352 KB |
testcase_18 | AC | 388 ms
101,180 KB |
testcase_19 | AC | 373 ms
101,248 KB |
testcase_20 | AC | 586 ms
101,196 KB |
testcase_21 | AC | 558 ms
101,228 KB |
testcase_22 | AC | 488 ms
101,228 KB |
testcase_23 | AC | 539 ms
101,352 KB |
testcase_24 | AC | 483 ms
101,188 KB |
testcase_25 | AC | 510 ms
101,196 KB |
testcase_26 | AC | 563 ms
101,244 KB |
testcase_27 | AC | 501 ms
101,204 KB |
testcase_28 | AC | 494 ms
101,184 KB |
testcase_29 | AC | 507 ms
101,204 KB |
testcase_30 | AC | 499 ms
101,212 KB |
ソースコード
//Let's join Kaede Takagaki Fan Club !! #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; #define pu push #define pb push_back #define eb emplace_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define a first #define b second #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,x) for(int i=0;i<x;i++) #define repn(i,x) for(int i=1;i<=x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) #define all(x) x.begin(),x.end() #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;} template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;} template<class t> using vc=vector<t>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.fi<<","<<p.sc<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } template<class T> void g(T &a){ cin >> a; } template<class T> void o(const T &a,bool space=false){ cout << a << (space?' ':'\n'); } //ios::sync_with_stdio(false); const ll mod = 998244353; //mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); template<class T> void add(T&a,T b){ a+=b; if(a >= mod) a-=mod; } ll modpow(ll x,ll n){ ll res=1; while(n>0){ if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res; } int pos[5005][5005], n, q, p, a[5005]; int main(){ ios::sync_with_stdio(false); cin >> n >> q >> p; repn(i, n) cin >> a[i]; rep(i, 5005) rep(j, 5005) pos[i][j] = INF; for(int i=n;i>=1;i--){ pos[i][a[i]] = i; rep(x, p){ chmin(pos[i][a[i]*x%p], pos[i+1][x]); chmin(pos[i][x], pos[i+1][x]); } } rep(i, q){ int l, r, k; cin >> l >> r >> k; if(pos[l][k] > r) cout<<"No"<<'\n'; else cout<<"Yes"<<'\n'; } }