Submission #68234

ソースコード

?
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
template< typename Monoid, typename OperatorMonoid, typename F, typename G, typename H >
struct LazySegmentTree {
int sz, height;
vector< Monoid > data;
vector< OperatorMonoid > lazy;
const F f;
const G g;
const H h;
const Monoid M1;
const OperatorMonoid OM0;
LazySegmentTree(int n, const F f, const G g, const H h,
const Monoid &M1, const OperatorMonoid OM0)
: f(f), g(g), h(h), M1(M1), OM0(OM0) {
sz = 1;
height = 0;
while(sz < n) sz <<= 1, height++;
data.assign(2 * sz, M1);
lazy.assign(2 * sz, OM0);
}
void set(int k, const Monoid &x) {
data[k + sz] = x;
}
void build() {
for(int k = sz - 1; k > 0; k--) {
data[k] = f(data[2 * k + 0], data[2 * k + 1]);
}
}
inline void propagate(int k) {
if(lazy[k] != OM0) {
lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
data[k] = apply(k);
lazy[k] = OM0;
}
}
inline Monoid apply(int k) {
return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]);
}
inline void recalc(int k) {
while(k >>= 1) data[k] = f(apply(2 * k + 0), apply(2 * k + 1));
}
inline void thrust(int k) {
for(int i = height; i > 0; i--) propagate(k >> i);
}
void update(int a, int b, const OperatorMonoid &x) {
if(a >= b) return;
thrust(a += sz);
thrust(b += sz - 1);
for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) lazy[l] = h(lazy[l], x), ++l;
if(r & 1) --r, lazy[r] = h(lazy[r], x);
}
recalc(a);
recalc(b);
}
Monoid query(int a, int b) {
if(a >= b) return M1;
thrust(a += sz);
thrust(b += sz - 1);
Monoid L = M1, R = M1;
for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) L = f(L, apply(l++));
if(r & 1) R = f(apply(--r), R);
}
return f(L, R);
}
Monoid operator[](const int &k) {
return query(k, k + 1);
}
template< typename C >
int find_subtree(int a, const C &check, Monoid &M, bool type) {
while(a < sz) {
propagate(a);
Monoid nxt = type ? f(apply(2 * a + type), M) : f(M, apply(2 * a + type));
if(check(nxt)) a = 2 * a + type;
else M = nxt, a = 2 * a + 1 - type;
}
return a - sz;
}
template< typename C >
int find_first(int a, const C &check) {
Monoid L = M1;
if(a <= 0) {
if(check(f(L, apply(1)))) return find_subtree(1, check, L, false);
return -1;
}
thrust(a + sz);
int b = sz;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) {
Monoid nxt = f(L, apply(a));
if(check(nxt)) return find_subtree(a, check, L, false);
L = nxt;
++a;
}
}
return -1;
}
template< typename C >
int find_last(int b, const C &check) {
Monoid R = M1;
if(b >= sz) {
if(check(f(apply(1), R))) return find_subtree(1, check, R, true);
return -1;
}
thrust(b + sz - 1);
int a = sz;
for(b += sz; a < b; a >>= 1, b >>= 1) {
if(b & 1) {
Monoid nxt = f(apply(--b), R);
if(check(nxt)) return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
};
template< typename Monoid, typename OperatorMonoid, typename F, typename G, typename H >
LazySegmentTree< Monoid, OperatorMonoid, F, G, H > get_lazy_segment_tree
(int N, const F &f, const G &g, const H &h, const Monoid &M1, const OperatorMonoid &OM0) {
return {N, f, g, h, M1, OM0};
}
struct Data {
ll Y;
ll D;
ll K;
ll YD;
ll DK;
ll YDK;
int len;
Data() : Y(0), D(0), K(0), YD(0), DK(0), YDK(0), len(0) {}
Data(ll Y, ll D, ll K, int len) : Y(Y), D(D), K(K), YD(0), DK(0), YDK(0), len(len) {}
Data(ll Y, ll D, ll K, ll YD, ll DK, ll YDK, int len) : Y(Y), D(D), K(K), YD(YD), DK(DK), YDK(YDK), len(len) {}
};
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, q;
string s;
cin >> n >> q >> s;
auto f = [](Data l, Data r) -> Data {
ll Y = l.Y + r.Y;
ll D = l.D + r.D;
ll K = l.K + r.K;
ll YD = l.YD + r.YD + l.Y * r.D;
ll DK = l.DK + r.DK + l.D * r.K;
ll YDK = l.YDK + r.YDK + l.Y * r.DK + l.YD * r.K;
int len = l.len + r.len;
return (Data(Y, D, K, YD, DK, YDK, len));
};
auto g = [](Data &data, char c) -> Data {
ll Y = data.len * (c == 'Y');
ll D = data.len * (c == 'D');
ll K = data.len * (c == 'K');
return (Data(Y, D, K, data.len));
};
auto h = [](char a, char b) -> char {
return (b);
};
auto seg = get_lazy_segment_tree(n, f, g, h, Data(), '~');
for (int i = 0; i < n; ++i) {
seg.set(i, Data(s[i] == 'Y', s[i] == 'D', s[i] == 'K', 1));
}
seg.build();
for (int i = 0; i < q; ++i) {
int l, r;
char c;
cin >> l >> r >> c;
seg.update(l - 1, r, c);
cout << seg.query(0, n).YDK << '\n';
}
return (0);
}

ステータス

項目 データ
問題 1522 - Douteki Programming
ユーザー名 ei1903
投稿日時 2021-08-31 12:52:15
言語 C++17
状態 Accepted
得点 5
ソースコード長 5725 Byte
最大実行時間 319 ms
最大メモリ使用量 73640 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 82 ms 15452 KB
1
in02.txt AC 94 ms 30160 KB
1
in03.txt AC 87 ms 8340 KB
1
in04.txt AC 60 ms 15720 KB
1
in05.txt AC 190 ms 16080 KB
1
in06.txt AC 281 ms 31452 KB
1
in07.txt AC 317 ms 31856 KB
1
in08.txt AC 281 ms 32392 KB
1
in09.txt AC 284 ms 32924 KB
1
in10.txt AC 277 ms 33460 KB
1
in11.txt AC 299 ms 36044 KB
1
in12.txt AC 288 ms 38744 KB
1
in13.txt AC 293 ms 41316 KB
1
in14.txt AC 288 ms 44028 KB
1
in15.txt AC 289 ms 46732 KB
1
in16.txt AC 263 ms 34716 KB
1
in17.txt AC 261 ms 37236 KB
1
in18.txt AC 268 ms 37700 KB
1
in19.txt AC 268 ms 40220 KB
1
in20.txt AC 235 ms 55280 KB
1
in21.txt AC 208 ms 56580 KB
1
in22.txt AC 219 ms 59672 KB
1
in23.txt AC 313 ms 62380 KB
1
in24.txt AC 319 ms 64960 KB
1
in25.txt AC 306 ms 67668 KB
1
in26.txt AC 311 ms 68204 KB
1
in27.txt AC 304 ms 68864 KB
1
in28.txt AC 253 ms 71188 KB
1
in29.txt AC 269 ms 73640 KB
1
in30.txt AC 40 ms 44460 KB
1
in31.txt AC 37 ms 44404 KB
1
in32.txt AC 51 ms 44736 KB
1
in33.txt AC 29 ms 44680 KB
1
in34.txt AC 27 ms 44884 KB
1
sample01.txt AC 21 ms 45088 KB
1
sample02.txt AC 22 ms 45040 KB
1