結果
問題 | No.749 クエリ全部盛り |
ユーザー | fumiphys |
提出日時 | 2019-03-06 00:32:44 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 873 ms / 3,000 ms |
コード長 | 4,559 bytes |
コンパイル時間 | 1,399 ms |
コンパイル使用メモリ | 115,096 KB |
実行使用メモリ | 156,036 KB |
最終ジャッジ日時 | 2023-09-05 19:00:58 |
合計ジャッジ時間 | 7,034 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 4 ms
4,380 KB |
testcase_06 | AC | 4 ms
4,380 KB |
testcase_07 | AC | 4 ms
4,380 KB |
testcase_08 | AC | 4 ms
4,376 KB |
testcase_09 | AC | 4 ms
4,380 KB |
testcase_10 | AC | 34 ms
5,340 KB |
testcase_11 | AC | 34 ms
5,176 KB |
testcase_12 | AC | 34 ms
5,128 KB |
testcase_13 | AC | 34 ms
5,120 KB |
testcase_14 | AC | 34 ms
5,176 KB |
testcase_15 | AC | 812 ms
155,904 KB |
testcase_16 | AC | 834 ms
155,920 KB |
testcase_17 | AC | 862 ms
155,976 KB |
testcase_18 | AC | 851 ms
156,028 KB |
testcase_19 | AC | 873 ms
156,036 KB |
ソースコード
// includes #include <cstdio> #include <cstdint> #include <iostream> #include <iomanip> #include <string> #include <queue> #include <stack> #include <vector> #include <set> #include <map> #include <unordered_map> #include <algorithm> #include <utility> #include <functional> #include <cmath> #include <climits> #include <bitset> #include <list> #include <random> // macros #define ll long long int #define pb emplace_back #define mk make_pair #define pq priority_queue #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define rep(i, n) FOR(i, 0, n) #define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--) #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) using namespace std; // types typedef pair<int, int> P; typedef pair<ll, int> Pl; typedef pair<ll, ll> Pll; typedef pair<double, double> Pd; // constants const int inf = 1e9; const ll linf = 1LL << 50; const double EPS = 1e-10; const int mod = 1e9 + 7; // solve template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;} template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;} template<typename T, typename E> struct LazySegmentTree_ { function<T(T, T)> f; function<E(E, E)> h; function<T(T, E, int)> p; int n; T def; E l_def; vector<T> vec; vector<E> lazy; LazySegmentTree_(){} LazySegmentTree_(int n_, function<T(T, T)> f_, T def_, function<E(E, E)> h_, E l_def_, function<T(T, E, int)> p_, vector<T> v=vector<T>()){ f = f_; h = h_; p = p_; def = def_; l_def = l_def_; // initialize vector n = 1; while(n < n_){ n *= 2; } vec = vector<T>(2*n-1, def); lazy = vector<E>(2*n-1, l_def); // initialize segment tree for(int i = 0; i < v.size(); i++){ vec[i + n - 1] = v[i]; } for(int i = n - 2; i >= 0; i--){ vec[i] = f(vec[2*i+1], vec[2*i+2]); } } void eval(int k, int len){ if(lazy[k] != l_def){ if(k < n - 1){ lazy[2*k+1] = h(lazy[2*k+1], lazy[k]); lazy[2*k+2] = h(lazy[2*k+2], lazy[k]); } vec[k] = p(vec[k], lazy[k], len); lazy[k] = l_def; } } E update(int a, int b, const E &val, int k, int l, int r){ eval(k, r - l); if(r <= a || b <= l){ return vec[k]; }else if(a <= l && r <= b){ lazy[k] = h(lazy[k], val); eval(k, r - l); return vec[k]; }else{ return vec[k] = f(update(a, b, val, 2*k+1, l, (l+r)/2), update(a, b, val, 2*k+2, (l+r)/2, r)); } } E update(int a, int b, E val){ return update(a, b, val, 0, 0, n); } // [l, r) -> [a, b) (at k) T query(int a, int b, int k, int l, int r){ eval(k, r - l); if(r <= a || b <= l)return def; if(a <= l && r <= b)return vec[k]; T ld = query(a, b, 2*k+1, l, (l+r)/2); T rd = query(a, b, 2*k+2, (l+r)/2, r); return f(ld, rd); } T query(int a, int b){ return query(a, b, 0, 0, n); } }; template<typename T, typename E> using LazySegmentTree = struct LazySegmentTree_<T, E>; using LazySegmentTreeI = LazySegmentTree<int, int>; struct Tr{ ll a, F, c; Tr(){} Tr(ll a, ll F, ll c): a(a), F(F), c(c){} Tr operator+(const Tr &r){ return Tr{(a*r.a + F*r.F + c*r.c) % mod, F, c}; } Tr operator*(const int &r){ return Tr{a % mod, F % mod, c * r % mod}; } bool operator==(const Tr &r) const{ return a == r.a && F == r.F && c == r.c; } bool operator!=(const Tr &r) const{ return !(*this == r); } }; ll fib[1000001]; int main(int argc, char const* argv[]) { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; fib[0] = 0; fib[1] = 1; for(int i = 2; i <= n; i++){ fib[i] = (fib[i-1] + fib[i-2]) % mod; } vector<Tr> vec(n); for(int i = 0; i < n; i++)vec[i] = Tr{0, fib[i], 1}; LazySegmentTree<Tr, Tr> seg = LazySegmentTree<Tr, Tr>(n, [](Tr a, Tr b){return Tr{(a.a + b.a) % mod, (a.F + b.F) % mod, (a.c + b.c) % mod};}, Tr{0, 0, 0}, [](Tr a, Tr b){return Tr{a.a*b.a%mod, (a.F*b.a+b.F)%mod, (a.c*b.a+b.c)%mod};}, Tr{1, 0, 0}, [](Tr a, Tr b, int c){return a + b;}, vec); rep(i, q){ int Q, l, r; ll k; cin >> Q >> l >> r >> k; if(Q == 0){ cout << k * seg.query(l, r + 1).a % mod << endl; }else if(Q == 1){ seg.update(l, r + 1, Tr{0, 0, k}); }else if(Q == 2){ seg.update(l, r + 1, Tr{1, 0, k}); }else if(Q == 3){ seg.update(l, r + 1, Tr{k, 0, 0}); }else{ seg.update(l, r + 1, Tr{1, k, 0}); } } return 0; }