結果
問題 |
No.2592 おでぶなおばけさん 2
|
ユーザー |
👑 ![]() |
提出日時 | 2023-12-20 01:09:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 122 ms / 2,500 ms |
コード長 | 1,681 bytes |
コンパイル時間 | 1,957 ms |
コンパイル使用メモリ | 110,512 KB |
最終ジャッジ日時 | 2025-02-18 12:27:47 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 83 |
ソースコード
/* 左端 l を固定して右に伸ばしてゆくとき、「一番右の要素に何を足せば重み和が 0 になるか」を管理するのは簡単。 K で割って A を引けばよい。 0 を入れたら 0 になる、のときクエリの答えは No 。 クエリを先読みし、右端 r で分類する。 * a[x] = (x を入れたら結果が 0 になるような l のリスト) という連想配列を作って r=1 から r=N まで走査する。 連想配列の要素数は log_K max|A| 程度で抑えられる。 */ #include <iostream> #include <string> #include <vector> #include <algorithm> #include <utility> #include <queue> #include <array> #include <cmath> using namespace std; using i64 = long long; #define rep(i,n) for(i64 i=0; i<(i64)(n); i++) const char* yn(bool x){ return x ? "Yes" : "No"; } #include <map> int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 N,Q,K; cin >> N >> Q >> K; vector<i64> A(N); for(int i=0; i<N; i++) cin >> A[i]; vector<int> L(Q), R(Q); rep(i,Q){ cin >> L[i] >> R[i]; L[i]--; } vector<vector<int>> queries(N+1); rep(i,Q) queries[R[i]].push_back(i); map<i64, vector<int>> bezero; vector<int> ans(Q); rep(i,N){ bezero[0].push_back(i); map<i64, vector<int>> nxbezero; for(auto& [u,v] : bezero) if(u % K == 0){ nxbezero[u/K - A[i]] = move(v); } swap(bezero, nxbezero); auto& tosearch = bezero[0]; for(auto qi : queries[i+1]){ ans[qi] = binary_search(tosearch.begin(), tosearch.end(), L[qi]) ? 0 : 1; } } rep(i,Q) cout << yn(ans[i]) << '\n'; return 0; }