結果
問題 | No.2592 おでぶなおばけさん 2 |
ユーザー |
![]() |
提出日時 | 2023-12-20 03:08:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 78 ms / 2,500 ms |
コード長 | 2,212 bytes |
コンパイル時間 | 3,706 ms |
コンパイル使用メモリ | 285,140 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-09-27 09:40:22 |
合計ジャッジ時間 | 13,568 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 83 |
ソースコード
#include<bits/stdc++.h>namespace {#pragma GCC diagnostic ignored "-Wunused-function"#include<atcoder/all>#pragma GCC diagnostic warning "-Wunused-function"using namespace std;using namespace atcoder;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)template<class S> bool chmax(S& a, const S& b) { if (a < b) { a = b; return true; } else return false; }template<class S> bool chmin(S& a, const S& b) { if (b < a) { a = b; return true; } else return false; }using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;default_random_engine gen(chrono::system_clock::now().time_since_epoch().count());template <int ...mods>struct MultiMod {tuple<dynamic_modint<mods>...> val;MultiMod() = default;MultiMod(integral auto x) {(..., (get<mods>(val) = x));}friend MultiMod operator+(const MultiMod& lhs, const MultiMod& rhs) {MultiMod res;res.val = tuple((get<mods>(lhs.val) + get<mods>(rhs.val))...);return res;}friend MultiMod operator-(const MultiMod& lhs, const MultiMod& rhs) {MultiMod res;res.val = tuple((get<mods>(lhs.val) - get<mods>(rhs.val))...);return res;}friend MultiMod operator*(const MultiMod& lhs, const MultiMod& rhs) {MultiMod res;res.val = tuple((get<mods>(lhs.val) * get<mods>(rhs.val))...);return res;}explicit operator bool() {return (... || get<mods>(val).val());}static void mod_init() {(..., dynamic_modint<mods>::set_mod(uniform_int_distribution<>(1, 2000001000)(gen)));}};} int main() {ios::sync_with_stdio(false);cin.tie(0);using S = MultiMod<0,1,2,3,4>;S::mod_init();int n, q;ll k_ll;cin >> n >> q >> k_ll;S k(k_ll);VL a(n);rep(i, n) cin >> a[i];vector<S> s(n + 1);rrep(i, n) {s[i] = s[i+1] * k + a[i];}vector<S> pow_k(n + 1);pow_k[0] = 1;rep(i, n) pow_k[i+1] = pow_k[i] * k;rep(_, q) {int l, r;cin >> l >> r;l--;S v = s[l] - s[r] * pow_k[r - l];cout << (v ? "Yes\n" : "No\n");}}