結果
問題 | No.2931 Shibuya 109 |
ユーザー | 👑 binap |
提出日時 | 2024-10-12 16:31:30 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,692 bytes |
コンパイル時間 | 5,089 ms |
コンパイル使用メモリ | 279,488 KB |
実行使用メモリ | 326,688 KB |
最終ジャッジ日時 | 2024-10-12 16:31:45 |
合計ジャッジ時間 | 15,245 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,096 ms
13,632 KB |
testcase_01 | TLE | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;using namespace atcoder;typedef long long ll;typedef vector<int> vi;typedef vector<long long> vl;typedef vector<vector<int>> vvi;typedef vector<vector<long long>> vvl;typedef long double ld;typedef pair<int, int> P;template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;}template <int m> istream& operator>>(istream& is, static_modint<m>& a) {long long x; is >> x; a = x; return is;}template <int m> istream& operator>>(istream& is, dynamic_modint<m>& a) {long long x; is >> x; a = x; return is;}template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); returnos;}template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : "");return os;}template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){returntrue;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n -1 ? "\n" : " "); return os;}template<typename T> void chmin(T& a, T b){a = min(a, b);}template<typename T> void chmax(T& a, T b){a = max(a, b);}// https://youtu.be/ylWYSurx10A?t=2352template<typename T>struct Matrix : vector<vector<T>> {int h, w;Matrix(int h, int w, T val=0): vector<vector<T>>(h, vector<T>(w, val)), h(h), w(w) {}Matrix(initializer_list<initializer_list<T>> a) : vector<vector<T>>(a.begin(), a.end()){assert(int(this->size()) >= 1);assert(int((*this)[0].size()) >= 1);h = this->size();w = (*this)[0].size();rep(i, h) assert(int((*this)[i].size()) == w);}Matrix& unit() {assert(h == w);rep(i,h) (*this)[i][i] = 1;return *this;}Matrix operator*=(const Matrix& M){assert(w == M.h);Matrix r(h, M.w);rep(i,h) rep(k,w) rep(j, M.w){r[i][j] += (*this)[i][k] * M[k][j];}swap(*this, r);return *this;}Matrix operator*(const Matrix& M) const {return (Matrix(*this) *= M);}};using S = Matrix<long long>;S op(S s1, S s2){return s2 * s1;}S e(){return S(3, 3).unit();}int main(){int n, q;cin >> n >> q;vector<int> a(n);cin >> a;vector<S> init;S mat0 = {{1, 0, 0}, {1, 1, 0}, {0, 0, 1}};S mat1 = {{1, 0, 1}, {1, 1, 0}, {0, 0, 1}};S mat9 = {{1, 0, 0}, {1, 1, 1}, {0, 0, 1}};rep(i, n){if(a[i] == 0) init.push_back(mat0);if(a[i] == 1) init.push_back(mat1);if(a[i] == 9) init.push_back(mat9);}segtree<S, op, e> seg(init);rep(i, q){int l, r;cin >> l >> r;l--; r--;auto res = seg.prod(l, r + 1);cout << res[1][2] << "\n";}return 0;}