結果

問題 No.749 クエリ全部盛り
ユーザー matsukin11111matsukin11111
提出日時 2019-11-08 12:21:46
言語 C++11
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 4,134 bytes
コンパイル時間 1,369 ms
コンパイル使用メモリ 86,436 KB
実行使用メモリ 85,376 KB
最終ジャッジ日時 2024-09-15 00:49:20
合計ジャッジ時間 5,275 ms
ジャッジサーバーID
(参考情報)
judge2 / judge6
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 WA -
testcase_03 WA -
testcase_04 RE -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility>
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
ll M = 1e9 + 7;
ll MOD = M;
//
//↓
typedef struct sayouso { ll p, q, r; }sayouso;
typedef struct atai { ll a, f; }atai;
//↑
typedef struct node { sayouso T; atai x; }node;
node lsegN[1 << 21], *lseg;
ll lsegNUM, lsegk;
//↓
sayouso id = { 1,0,0 };
atai xx(atai x, atai y) {
atai ret;
ret.a = (x.a + y.a) % M;
ret.f = (x.f + y.f) % M;
return ret;
}
atai Tx(sayouso T, atai x) {
atai ret;
ret.a = (T.p*x.a + T.q*x.f + T.r) % M;
ret.f = x.f;
return ret;
}
sayouso TT(sayouso S, sayouso T) {
sayouso ret;
ret.p = S.p*T.p%M;
ret.q = (S.p*T.q + S.q) % M;
ret.r = (S.p*T.r + S.r) % M;
return ret;
}
sayouso fT(sayouso T, ll k) {
sayouso ret;
ret.p = T.p;
ret.q = T.q;
ret.r = (T.r << k) % M;
return ret;
}
//↑
void lseguse(ll n) {
lsegNUM = n;
lseg = lsegN + lsegNUM;
lsegk = 0; while (n /= 2)lsegk++;
}
void lseginit() {
for (ll i = lsegNUM - 1; i>0; i--)lsegN[i].x = xx(lsegN[2 * i].x, lsegN[2 * i + 1].x);
rep(i, 1, 2 * lsegNUM)lsegN[i].T = id;
}
void lsegupdatesub(ll l, ll r, sayouso T, ll i, ll cl, ll cr, ll ck) {
//disjoint
if (cr <= l || r <= cl)return;
//
if (l <= cl && cr <= r) {
lsegN[i].T = TT(T, lsegN[i].T);
return;
}
//
//
lsegN[2 * i].T = TT(lsegN[i].T, lsegN[2 * i].T);
lsegN[2 * i + 1].T = TT(lsegN[i].T, lsegN[2 * i + 1].T);
//
ll cm = (cl + cr) / 2;
lsegupdatesub(l, r, T, 2 * i, cl, cm, ck - 1);
lsegupdatesub(l, r, T, 2 * i + 1, cm, cr, ck - 1);
//node
lsegN[i].x = xx(Tx(fT(lsegN[2 * i].T, ck - 1), lsegN[2 * i].x), Tx(fT(lsegN[2 * i + 1].T, ck - 1), lsegN[2 * i + 1].x));
lsegN[i].T = id;
}
void lsegupdate(ll l, ll r, sayouso T) { lsegupdatesub(l, r, T, 1, 0, lsegNUM, lsegk); }
atai lsegcalcsub(ll l, ll r, ll i, ll cl, ll cr, ll ck) {
//
if (l <= cl && cr <= r)return Tx(fT(lsegN[i].T, ck), lsegN[i].x);
ll cm = (cl + cr) / 2;
//()
lsegN[2 * i].T = TT(lsegN[i].T, lsegN[2 * i].T);
lsegN[2 * i + 1].T = TT(lsegN[i].T, lsegN[2 * i + 1].T);
lsegN[i].x = Tx(fT(lsegN[i].T, ck), lsegN[i].x);
lsegN[i].T = id;
//
if (r <= cm)return lsegcalcsub(l, r, 2 * i, cl, cm, ck - 1);
//
if (cm <= l)return lsegcalcsub(l, r, 2 * i + 1, cm, cr, ck - 1);
//
return xx(lsegcalcsub(l, r, 2 * i, cl, cm, ck - 1), lsegcalcsub(l, r, 2 * i + 1, cm, cr, ck - 1));
}
atai lsegcalc(ll l, ll r) { return lsegcalcsub(l, r, 1, 0, lsegNUM, lsegk); }
//
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> Q;
lseguse(1 << 20);
lsegN[1].x.f = 1;
for (int i = 2; i < 1000100; i++)lsegN[i].x.f = (lsegN[i - 1].x.f + lsegN[i-2].x.f) % MOD;
lseginit();
for (int i = 0; i < Q; i++) {
ll q, l, r, k;
sayouso T;
cin >> q >> l >> r >> k;
if (q == 0)puts(lsegcalc(l, r + 1).a*k%MOD);
else if (q == 1) {
T.p = 0; T.q = 0; T.r = k;
lsegupdate(l,r+1,T);
}
else if (q == 2) {
T.p = 1; T.q = 0; T.r = k;
lsegupdate(l, r + 1, T);
}
else if (q == 3) {
T.p = k; T.q = 0; T.r = 0;
lsegupdate(l, r + 1, T);
}
else if (q == 4) {
T.p = 1; T.q = k; T.r = 0;
lsegupdate(l, r + 1, T);
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0