Submission #64637

ソースコード

?
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
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
//SegmentTree{{{
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};
}
//}}}
signed main(){
/*
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
*/
int h, w, n;
cin >> h >> w >> n;
vector<tuple<int, int, int> > point;
for(int i = 0; i < n; ++i){
int y, x, p;
cin >> y >> x >> p;
point.emplace_back(y-1, x-1, p);
}
sort(point.begin(), point.end());
auto rmq = get_segment_tree(w, [](auto a, auto b){ return max(a, b); }, 0LL);
for(auto [y, x, p] : point){
rmq.update(x, max<int>(rmq[x], rmq.query(0, x + 1) + p));
}
cout << rmq.query(0, w) << '\n';
return (0);
}

ステータス

項目 データ
問題 1436 - Simple Grid Problem
ユーザー名 ei1903
投稿日時 2020-11-07 15:43:06
言語 C++17
状態 Accepted
得点 6
ソースコード長 3015 Byte
最大実行時間 193 ms
最大メモリ使用量 11100 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 139 ms 8012 KB
1
in02.txt AC 60 ms 2104 KB
1
in03.txt AC 96 ms 3732 KB
1
in04.txt AC 139 ms 8604 KB
1
in05.txt AC 33 ms 5132 KB
1
in06.txt AC 180 ms 10332 KB
1
in07.txt AC 182 ms 9992 KB
1
in08.txt AC 173 ms 10040 KB
1
in09.txt AC 193 ms 9612 KB
1
in10.txt AC 175 ms 9604 KB
1
in11.txt AC 180 ms 10884 KB
1
in12.txt AC 183 ms 9572 KB
1
in13.txt AC 152 ms 9620 KB
1
in14.txt AC 152 ms 10084 KB
1
in15.txt AC 31 ms 4700 KB
1
in16.txt AC 20 ms 4668 KB
1
in17.txt AC 24 ms 4764 KB
1
in18.txt AC 150 ms 7788 KB
1
in19.txt AC 141 ms 8024 KB
1
in20.txt AC 151 ms 7264 KB
1
in21.txt AC 149 ms 7572 KB
1
in22.txt AC 167 ms 9512 KB
1
in23.txt AC 185 ms 10396 KB
1
in24.txt AC 174 ms 10224 KB
1
in25.txt AC 178 ms 10896 KB
1
in26.txt AC 175 ms 9988 KB
1
in27.txt AC 169 ms 9396 KB
1
in28.txt AC 171 ms 10672 KB
1
in29.txt AC 180 ms 9624 KB
1
in30.txt AC 165 ms 9580 KB
1
in31.txt AC 53 ms 5620 KB
1
in32.txt AC 130 ms 7568 KB
1
in33.txt AC 139 ms 7908 KB
1
in34.txt AC 14 ms 628 KB
1
in35.txt AC 171 ms 10820 KB
1
in36.txt AC 189 ms 11100 KB
1
in37.txt AC 171 ms 9644 KB
1
in38.txt AC 21 ms 696 KB
1
in39.txt AC 19 ms 668 KB
1
in40.txt AC 21 ms 640 KB
1
in41.txt AC 172 ms 10440 KB
1
in42.txt AC 170 ms 9548 KB
1
sample01.txt AC 27 ms 724 KB
1
sample02.txt AC 21 ms 700 KB
1