Submission #64734

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
using namespace std;
vector<int64_t> b; //累積和してセグ木内で使うのでグローバルで宣言する
struct LazySegmentTree{
int n, sz;
vector<int64_t> node; //値配列
vector<int> lazy; //遅延配列(左端の差を格納する)
int64_t e1 = 0LL; //単位元(値)
int e2 = INT_MAX; //単位元(遅延)
LazySegmentTree(vector<int64_t> &v){
n = v.size();
sz = 1;
while(sz < n) sz <<= 1; //nを超えない最大の2羃
node.resize(sz * 2 - 1, e1);
lazy.resize(sz * 2 - 1, e2);
for(int i = 0; i < n; ++i){
node[i + sz - 1] = v[i];
}
for(int i = sz - 2; i >= 0; --i){
node[i] = node[i * 2 + 1] + node[i * 2 + 2];
}
}
// [l, r) 半開区間で実装
void update(int l, int r, int x){
update(l, r, x, 0, 0, sz);
}
void update(int l, int r, int x, int k, int u, int v){
// 伝播
eval(k, u, v - 1);
// 完全に被らないなら見ない
if(r <= u || v <= l) return;
// 完全に被るなら遅延配列を更新し伝播
if(l <= u && v <= r){
lazy[k] = x;
eval(k, u, v - 1);
}else{
update(l, r, x, k * 2 + 1, u, (u + v) / 2); // 左の子へ
update(l, r, x, k * 2 + 2, (u + v) / 2, v); // 右の子へ
node[k] = node[k * 2 + 1] + node[k * 2 + 2]; // 左右の子の更新が終わったら値配列を更新
}
return;
}
// [l, r) 半開区間で実装
int64_t sum(int l, int r){
return (sum(l, r, 0, 0, sz));
}
int64_t sum(int l, int r, int k, int u, int v){
if(r <= u || v <= l) return (0); // 完全に被らないなら0を返す
eval(k, u, v - 1); // 伝播
if(l <= u && v <= r) return (node[k]); // 完全に区間に被るなら値を返す
int64_t vl = sum(l, r, k * 2 + 1, u, (u + v) / 2); // 左の子へ
int64_t vr = sum(l, r, k * 2 + 2, (u + v) / 2, v); // 右の子へ
return (vl + vr);
}
// 伝播を行う
// 引数はノード番号、ノードの担当する区間の左端、区間の右端
void eval(int k, int l, int r){
// lazy[k]が単位元でない＝伝播する値がある
if(lazy[k] != e2){
l = l + lazy[k]; // bの左端
r = r + lazy[k]; // bの右端
node[k] = b[r] - b[l - 1]; // 値配列にbの区間和を加算
// ノードkが最下段でなければ伝播
if(k < sz - 1){
lazy[k * 2 + 1] = lazy[k];
lazy[k * 2 + 2] = lazy[k];
}
lazy[k] = e2; // 伝播し終わったので単位元に戻す
}
return;
}
};
signed main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int64_t> a(n + 1);
b.resize(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
for(int i = 1; i <= n; ++i){
cin >> b[i];
b[i] += b[i-1];
}
LazySegmentTree seg(a); // 配列aで初期化
for(int i = 0; i < m; ++i){
int op;
cin >> op;
if(op == 0){
int x, y, z;
cin >> x >> y >> z;
seg.update(x, x + z, y - x); // クエリで左端の差を与える
}else{
int p, q;
cin >> p >> q;
cout << seg.sum(p, q + 1) << '\n';
}
}
return (0);
}

ステータス

項目 データ
問題 1446 - Copy&Sum
ユーザー名 syoribu
投稿日時 2020-11-15 22:39:49
言語 C++17
状態 Accepted
得点 12
ソースコード長 3714 Byte
最大実行時間 195 ms
最大メモリ使用量 17800 KB

セット

セット 得点 Cases
1 ALL 12 / 12 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 22 ms 600 KB
1
in2 AC 23 ms 612 KB
1
in3 AC 16 ms 8592 KB
1
in4 AC 18 ms 8544 KB
1
in5 AC 20 ms 8628 KB
1
in6 AC 26 ms 8460 KB
1
in7 AC 24 ms 8532 KB
1
in8 AC 28 ms 8488 KB
1
in9 AC 19 ms 8576 KB
1
in10 AC 23 ms 688 KB
1
in11 AC 19 ms 516 KB
1
in12 AC 25 ms 600 KB
1
in13 AC 21 ms 552 KB
1
in14 AC 17 ms 500 KB
1
in15 AC 20 ms 576 KB
1
in16 AC 19 ms 396 KB
1
in17 AC 18 ms 468 KB
1
in18 AC 19 ms 524 KB
1
in19 AC 27 ms 560 KB
1
in20 AC 21 ms 696 KB
1
in21 AC 170 ms 10712 KB
1
in22 AC 195 ms 12128 KB
1
in23 AC 168 ms 13804 KB
1
in24 AC 180 ms 15088 KB
1
in25 AC 133 ms 16376 KB
1
in26 AC 139 ms 17800 KB
1