結果
問題 | No.1219 Mancala Combo |
ユーザー |
![]() |
提出日時 | 2023-01-23 02:37:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 266 ms / 2,000 ms |
コード長 | 3,420 bytes |
コンパイル時間 | 1,180 ms |
コンパイル使用メモリ | 115,276 KB |
最終ジャッジ日時 | 2025-02-10 06:27:52 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <iostream>#include <vector>#include <cmath>#include <map>#include <set>#include <iomanip>#include <queue>#include <algorithm>#include <numeric>#include <deque>#include <complex>//https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_Husing namespace std;template<class S, S (*op)(S, S), S (*e)(),class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>struct LazySegTree {vector<S> seg;vector<F> lazy;long long N = 1;LazySegTree (long long n) : LazySegTree(vector<S>(n, e())) {}LazySegTree (const vector<S> &v){long long n = v.size();while (N < n) N *= 2;seg.resize(N*2-1, e());lazy.resize(N*2-1, id());for (long long i=0; i<n; i++) seg[i+N-1] = v[i];for (long long i=N-2; i>=0; i--){seg[i] = op(seg[i*2+1], seg[i*2+2]);}}void eval (long long idx, long long bitl, long long bitr){if (lazy[idx] != id()){seg[idx] = mapping(lazy[idx], seg[idx]);if (bitl != bitr){lazy[2*idx+1] = composition(lazy[idx], lazy[2*idx+1]);lazy[2*idx+2] = composition(lazy[idx], lazy[2*idx+2]);}lazy[idx] = id();}}//a[i] -> f(a[i]) for l<=i<=rvoid set (long long l, long long r, F val){_set(l, r, val, 0, 0, N-1);}void _set (long long l, long long r, F val, long long idx, long long bitl, long long bitr){eval(idx, bitl, bitr);if (r < bitl || l > bitr) return;if (l <= bitl && bitr <= r){lazy[idx] = composition(lazy[idx], val);eval(idx, bitl, bitr);}else{long long bitm = (bitl+bitr)/2;_set(l, r, val, idx*2+1, bitl, bitm);_set(l, r, val, idx*2+2, bitm+1, bitr);seg[idx] = op(seg[idx*2+1], seg[idx*2+2]);}}//op(a[l], ..., a[r])S prod (long long l, long long r) {return _prod(l, r, 0, 0, N-1);}S all_prod() const{return seg[0];}S _prod (long long l, long long r, long long idx, long long bitl, long long bitr) {if (r < bitl || l > bitr) return e();eval(idx, bitl, bitr);if (l <= bitl && bitr <= r) return seg[idx];long long bitm = (bitl+bitr)/2;return op(_prod(l, r, idx*2+1, bitl, bitm), _prod(l, r, idx*2+2, bitm+1, bitr));}S get (long long i) {return prod(i, i);}void show() const{for (int i=0; i<N*2-1; i++) cout << seg[i] << " ";for (int i=0; i<N*2-1; i++) cout << lazy[i] << " ";}};struct S{long long val;long long len;};using F = long long;S op(S a, S b){ return {a.val + b.val, a.len + b.len}; }S e(){ return {0, 0}; }S mapping(F f, S x){ return {x.val + x.len*f, x.len}; }F composition(F f, F g){ return f+g; }F id(){ return 0; }int main(){long long N, A, B;cin >> N;vector<S> v(N+1, {0, 1});LazySegTree<S, op, e, F, mapping, composition, id> tree(v);for (int i=1; i<=N; i++){cin >> A;tree.set(i, i, A);}for (long long i=N; i>=1; i--){B = tree.get(i).val;if (B % i != 0){cout << "No" << endl;return 0;}tree.set(i, i, -B);tree.set(0, i-1, B/i);}cout << "Yes" << endl;return 0;}