Submission #64749

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
typedef long long SEGNODE_TYPE; // セグ木のノードの型の定義
class Segtree
{
public:
SEGNODE_TYPE monoid;
int segsize; // セグ木の大きさ
vector<SEGNODE_TYPE> value;
// [引数]
// int n : 大きさ
// SEGNODE_TYPE start : 初期値
// SEGNODE_TYPE mnd : 単位元（モノイド）
// [動作]
// セグ木を作る
// ※SEGNODE_TYPE の定義を忘れずに
Segtree() {}
Segtree(int n, SEGNODE_TYPE start, SEGNODE_TYPE mnd) {
segsize = 1;
while(segsize < n){
segsize = segsize * 2;
}
value = vector<SEGNODE_TYPE>(2 * segsize - 1, start);
monoid = mnd;
}
// [引数]
// int i : 変更箇所
// SEGNODE_TYPE x : 変更値
// [動作]
// 場所iをxに変更
void UpDate(int i, SEGNODE_TYPE x) {
i += segsize - 1;
value[i] = x;
while(i > 0){
i = (i-1) / 2;
value[i] = Requirement(value[i * 2 + 1], value[i * 2 + 2]);
}
return;
}
// [引数]
// int a : 区間の左端
// int b : 区間の右端
// [動作]
// 区間[a, b)のクエリを処理する（SegQueryへ橋渡し）
// ※呼び出す際にはSEGNODE_TYPE Requirement(SEGNODE_TYPE x, SEGNODE_TYPE y)の中身を確認
SEGNODE_TYPE Query(int a, int b) {
return ( SegQuery(a, b, 0, 0, segsize) );
}
// [引数]
// int a : クエリの範囲の左端
// int b : クエリの範囲の右端
// int k : 今いるノードの場所
// int l : 今いるノードの参照範囲の左端
// int r : 今いるノードの参照範囲の右端
// [動作]
// 区間[a, b)のクエリを求める
SEGNODE_TYPE SegQuery(int a, int b, int k, int l, int r) {
// [a, b)の区間に対するクエリについて、ノードk(区間[l, r)担当)が答える
if(r <= a || b <= l) {
return (monoid);
}
if(a <= l && r <= b){
// ノードkの担当クエリ区間[a ,b)に完全に含まれる
return (value[k]);
}
else {
// 左右の子に尋ねる
SEGNODE_TYPE c1 = SegQuery(a, b, 2*k+1, l, (l+r)/2); // 左の子（状況に合わせて型を変える）
SEGNODE_TYPE c2 = SegQuery(a, b, 2*k+2, (l+r)/2, r); // 右の子（状況に合わせて型を変える）
return ( Requirement(c1, c2) ); // 左右の子から求めたいものを返す
}
}
// 求めたいもの（最小値ならmin(x, y)、最大値ならmax(x, y)、合計値なら(x + y)など）
// ※ここのreturn文は用途に合わせて書き換える必要がある
SEGNODE_TYPE Requirement(SEGNODE_TYPE x, SEGNODE_TYPE y) {
return ( max(x, y) );
}
// [引数]
// int i : 場所
// [動作]
// 左からi番目の値を変えす
SEGNODE_TYPE GetReaf(int i) {
return( value[i + segsize - 1] );
}
};
signed main() {
int h, w, n;
int y, x;
long long p;
long long ans;
vector<pair<int, int> > pos;
map<pair<int, int>, long long> point;
pair<int, int> loc;
cin >> h >> w >> n;
Segtree value = Segtree(w, 0, 0);
for ( int i = 0; i < n; i++ ) {
cin >> y >> x >> p;
y--;
x--;
loc = make_pair(y, x);
pos.push_back(loc);
point[loc] = p;
}
sort(pos.begin(), pos.end());
ans = 0;
for ( int i = 0; i < n; i++ ) {
loc = pos[i];
value.UpDate(loc.second, value.Query(0, 1+loc.second)+point[loc]);
ans = max(ans, value.GetReaf(loc.second));
}
cout << ans << endl;
return (0);
}

ステータス

項目 データ
問題 1436 - Simple Grid Problem
ユーザー名 ei1929
投稿日時 2020-11-16 18:19:20
言語 C++
状態 Accepted
得点 6
ソースコード長 4177 Byte
最大実行時間 407 ms
最大メモリ使用量 19320 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 243 ms 13256 KB
1
in02.txt AC 88 ms 5188 KB
1
in03.txt AC 162 ms 9640 KB
1
in04.txt AC 240 ms 15288 KB
1
in05.txt AC 37 ms 8612 KB
1
in06.txt AC 316 ms 18584 KB
1
in07.txt AC 407 ms 18688 KB
1
in08.txt AC 316 ms 18664 KB
1
in09.txt AC 315 ms 18764 KB
1
in10.txt AC 324 ms 18740 KB
1
in11.txt AC 331 ms 18720 KB
1
in12.txt AC 319 ms 18692 KB
1
in13.txt AC 281 ms 18668 KB
1
in14.txt AC 284 ms 18640 KB
1
in15.txt AC 28 ms 8764 KB
1
in16.txt AC 25 ms 8860 KB
1
in17.txt AC 26 ms 8824 KB
1
in18.txt AC 245 ms 14660 KB
1
in19.txt AC 245 ms 14624 KB
1
in20.txt AC 246 ms 14588 KB
1
in21.txt AC 255 ms 14556 KB
1
in22.txt AC 307 ms 18760 KB
1
in23.txt AC 305 ms 18732 KB
1
in24.txt AC 313 ms 18832 KB
1
in25.txt AC 294 ms 19320 KB
1
in26.txt AC 300 ms 19200 KB
1
in27.txt AC 311 ms 18696 KB
1
in28.txt AC 310 ms 18672 KB
1
in29.txt AC 302 ms 18772 KB
1
in30.txt AC 308 ms 18872 KB
1
in31.txt AC 62 ms 8740 KB
1
in32.txt AC 226 ms 12892 KB
1
in33.txt AC 261 ms 14620 KB
1
in34.txt AC 20 ms 524 KB
1
in35.txt AC 296 ms 18796 KB
1
in36.txt AC 297 ms 18768 KB
1
in37.txt AC 311 ms 18744 KB
1
in38.txt AC 30 ms 548 KB
1
in39.txt AC 24 ms 520 KB
1
in40.txt AC 21 ms 620 KB
1
in41.txt AC 289 ms 18768 KB
1
in42.txt AC 295 ms 18744 KB
1
sample01.txt AC 16 ms 680 KB
1
sample02.txt AC 17 ms 648 KB
1