Submission #68570

ソースコード

?
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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
template< typename Monoid, typename F >
struct SegmentTree {
int sz;
vector< Monoid > seg;
const F f;
const Monoid M1;
SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
sz = 1;
while(sz < n) sz <<= 1;
seg.assign(2 * sz, M1);
}
void set(int k, const Monoid &x) {
seg[k + sz] = x;
}
void build() {
for(int k = sz - 1; k > 0; k--) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
void update(int k, const Monoid &x) {
k += sz;
seg[k] = x;
while(k >>= 1) {
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
}
Monoid query(int a, int b) {
Monoid L = M1, R = M1;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) L = f(L, seg[a++]);
if(b & 1) R = f(seg[--b], R);
}
return f(L, R);
}
Monoid operator[](const int &k) const {
return seg[k + sz];
}
template< typename C >
int find_subtree(int a, const C &check, Monoid &M, bool type) {
while(a < sz) {
Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[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, seg[1]))) return find_subtree(1, check, L, false);
return -1;
}
int b = sz;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) {
Monoid nxt = f(L, seg[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(seg[1], R))) return find_subtree(1, check, R, true);
return -1;
}
int a = sz;
for(b += sz; a < b; a >>= 1, b >>= 1) {
if(b & 1) {
Monoid nxt = f(seg[--b], R);
if(check(nxt)) return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
};
template< typename Monoid, typename F >
SegmentTree< Monoid, F > get_segment_tree(int N, const F& f, const Monoid& M1) {
return {N, f, M1};
}
struct Data {
int ans, l, r, all;
Data() : ans(0), l(0), r(0), all(0) {}
Data(int ans, int l, int r, int all) : ans(ans), l(l), r(r), all(all) {}
};
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, q;
cin >> n >> q;
auto f = [](Data a, Data b) -> Data {
int ans = max({a.ans, b.ans, a.r + b.l});
int l = a.l + a.all * b.l;
int r = a.r * b.all + b.r;
int all = a.all & b.all;
return (Data(ans, l, r, all));
};
auto seg = get_segment_tree(n, f, Data());
for (int i = 0; i < n; ++i) seg.set(i, Data(1, 1, 1, 1));
seg.build();
for (int i = 0; i < q; ++i) {
int k;
cin >> k;
--k;
seg.update(k, Data());
cout << seg.query(0, n).ans << '\n';
}
return (0);
}

ステータス

項目 データ
問題 1528 - Monochrome Balls
ユーザー名 ei1903
投稿日時 2021-09-23 16:36:34
言語 C++17
状態 Accepted
得点 4
ソースコード長 3578 Byte
最大実行時間 122 ms
最大メモリ使用量 35680 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 23 ms 732 KB
1
in02.txt AC 19 ms 416 KB
1
in03.txt AC 24 ms 596 KB
1
in04.txt AC 21 ms 536 KB
1
in05.txt AC 15 ms 552 KB
1
in06.txt AC 29 ms 8752 KB
1
in07.txt AC 37 ms 1652 KB
1
in08.txt AC 46 ms 9016 KB
1
in09.txt AC 32 ms 9088 KB
1
in10.txt AC 66 ms 9672 KB
1
in11.txt AC 60 ms 18188 KB
1
in12.txt AC 107 ms 19028 KB
1
in13.txt AC 51 ms 19356 KB
1
in14.txt AC 49 ms 19420 KB
1
in15.txt AC 40 ms 19624 KB
1
in16.txt AC 98 ms 20464 KB
1
in17.txt AC 56 ms 20792 KB
1
in18.txt AC 100 ms 21632 KB
1
in19.txt AC 122 ms 22540 KB
1
in20.txt AC 112 ms 23380 KB
1
in21.txt AC 102 ms 24092 KB
1
in22.txt AC 116 ms 24932 KB
1
in23.txt AC 114 ms 25644 KB
1
in24.txt AC 115 ms 26480 KB
1
in25.txt AC 91 ms 28476 KB
1
in26.txt AC 83 ms 30468 KB
1
in27.txt AC 76 ms 32336 KB
1
in28.txt AC 91 ms 34460 KB
1
in29.txt AC 85 ms 35680 KB
1
in30.txt AC 38 ms 27684 KB
1
in31.txt AC 21 ms 19312 KB
1
sample.txt AC 25 ms 19392 KB
1