Submission #68558

ソースコード

?
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
#include <iostream>
#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 {
long long left;
long long right;
bool increasing;
Data() : left(INT64_MAX), right(INT64_MIN), increasing(true) {}
Data(long long val) : left(val), right(val), increasing(true) {}
Data(long long left, long long right, bool increasing) : left(left), right(right), increasing(increasing) {}
};
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<long long> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
auto f = [](Data a, Data b) -> Data {
long long left = a.left;
long long right = b.right;
bool increasing = a.increasing && b.increasing && a.right <= b.left;
return (Data(left, right, increasing));
};
auto seg = get_segment_tree(n, f, Data());
for (int i = 0; i < n; ++i) seg.set(i, Data(a[i]));
seg.build();
int res = 0;
for(int i = 0; i < q; ++i){
int x, v;
cin >> x >> v;
--x;
a[x] += v;
seg.update(x, Data(a[x]));
if (seg.query(0, n).increasing) {
++res;
}
}
cout << res << '\n';
return (0);
}

ステータス

項目 データ
問題 1530 - Increasing Sequence 2
ユーザー名 ei1903
投稿日時 2021-09-23 11:07:20
言語 C++17
状態 Accepted
得点 3
ソースコード長 3921 Byte
最大実行時間 183 ms
最大メモリ使用量 27672 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 31 ms 600 KB
1
in02.txt AC 17 ms 428 KB
1
in03.txt AC 23 ms 508 KB
1
in04.txt AC 30 ms 460 KB
1
in05.txt AC 23 ms 540 KB
1
in06.txt AC 26 ms 876 KB
1
in07.txt AC 22 ms 744 KB
1
in08.txt AC 15 ms 604 KB
1
in09.txt AC 21 ms 756 KB
1
in10.txt AC 22 ms 852 KB
1
in11.txt AC 32 ms 7624 KB
1
in12.txt AC 94 ms 14728 KB
1
in13.txt AC 30 ms 7692 KB
1
in14.txt AC 55 ms 14708 KB
1
in15.txt AC 147 ms 27292 KB
1
in16.txt AC 168 ms 27400 KB
1
in17.txt AC 161 ms 27560 KB
1
in18.txt AC 158 ms 27472 KB
1
in19.txt AC 157 ms 27508 KB
1
in20.txt AC 158 ms 27672 KB
1
in21.txt AC 144 ms 27580 KB
1
in22.txt AC 154 ms 27612 KB
1
in23.txt AC 146 ms 27520 KB
1
in24.txt AC 122 ms 27560 KB
1
in25.txt AC 127 ms 27596 KB
1
in26.txt AC 134 ms 27376 KB
1
in27.txt AC 165 ms 27668 KB
1
in28.txt AC 55 ms 688 KB
1
in29.txt AC 183 ms 27648 KB
1
in30.txt AC 160 ms 27552 KB
1
in31.txt AC 149 ms 27588 KB
1
in32.txt AC 155 ms 27492 KB
1
in33.txt AC 158 ms 27532 KB
1
in34.txt AC 150 ms 27572 KB
1
in35.txt AC 95 ms 2392 KB
1
in36.txt AC 153 ms 27500 KB
1
sample.txt AC 21 ms 620 KB
1