Submission #64766

ソースコード

?
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
#include <bits/stdc++.h>
//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (n - 1); i > (a - 1); --i)
#define arep(i, x) for (auto &&i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
#define rirep(i, x) for (auto i = (x).rbegin(); i != (x).rend(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
// gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1LL << (n))
#define pcnt(x) __builtin_popcountll(x)
//配列内等要素削除
#define Unique(x) (x).erase(unique((x).begin(), (x).end()), (x).end())
#define Fixed(n) fixed << setprecision(n)
//総和
#define sowa(n) (((n) * ((n) + 1)) / 2)
#define updiv(a, b) ((a + b - 1) / b)
#define cauto const auto &
using P = pair<int, int>;
using Graph = vector<vector<P>>;
template <class T> //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T> //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) { //多次元初期化
std::fill((T *)array, (T *)(array + N), val);
}
template <class A, class B>
bool chmax(A &a, const B &b) { //最大値更新 返り値はbool
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class A, class B>
bool chmin(A &a, const B &b) { //最小値更新 返り値はbool int a, b;
if (b < a) {
a = b;
return 1;
}
return 0;
}
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, 1, 1, -1, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END
template <typename Monoid>
struct SegmentTree {
using F = function<Monoid(Monoid, Monoid)>;
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;
}
};
signed main(void) {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int h, w, n;
cin >> h >> w >> n;
vector<int> ans(w + 1, 0);
SegmentTree<int> seg(
w + 1, [](int a, int b) { return max(a, b); }, 0);
vector<tuple<int, int, int>> tup;
rep(i, 0, n) {
int y, x, p;
cin >> y >> x >> p;
tup.emplace_back(y, x, p);
}
sort(all(tup));
rep(i, 0, n) {
seg.update(get<1>(tup[i]),
get<2>(tup[i]) + seg.query(0, get<1>(tup[i]) + 1));
ans[get<1>(tup[i])] = seg.query(0, get<1>(tup[i]) + 1);
}
cout << *max_element(all(ans)) << '\n';
return 0;
}

ステータス

項目 データ
問題 1436 - Simple Grid Problem
ユーザー名 immunity
投稿日時 2020-11-17 18:50:23
言語 C++17
状態 Accepted
得点 6
ソースコード長 4785 Byte
最大実行時間 122 ms
最大メモリ使用量 14556 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 92 ms 7372 KB
1
in02.txt AC 51 ms 2320 KB
1
in03.txt AC 64 ms 3644 KB
1
in04.txt AC 93 ms 13980 KB
1
in05.txt AC 26 ms 6280 KB
1
in06.txt AC 114 ms 13828 KB
1
in07.txt AC 122 ms 13520 KB
1
in08.txt AC 112 ms 14360 KB
1
in09.txt AC 113 ms 14556 KB
1
in10.txt AC 110 ms 12816 KB
1
in11.txt AC 120 ms 12672 KB
1
in12.txt AC 113 ms 13540 KB
1
in13.txt AC 109 ms 13492 KB
1
in14.txt AC 102 ms 13960 KB
1
in15.txt AC 22 ms 6368 KB
1
in16.txt AC 22 ms 6420 KB
1
in17.txt AC 30 ms 6216 KB
1
in18.txt AC 83 ms 6892 KB
1
in19.txt AC 87 ms 7144 KB
1
in20.txt AC 79 ms 8716 KB
1
in21.txt AC 86 ms 7752 KB
1
in22.txt AC 108 ms 13572 KB
1
in23.txt AC 119 ms 13052 KB
1
in24.txt AC 111 ms 14240 KB
1
in25.txt AC 105 ms 13300 KB
1
in26.txt AC 108 ms 14032 KB
1
in27.txt AC 115 ms 12568 KB
1
in28.txt AC 114 ms 13428 KB
1
in29.txt AC 109 ms 12744 KB
1
in30.txt AC 93 ms 13308 KB
1
in31.txt AC 41 ms 7988 KB
1
in32.txt AC 67 ms 8728 KB
1
in33.txt AC 67 ms 7948 KB
1
in34.txt AC 19 ms 644 KB
1
in35.txt AC 103 ms 14400 KB
1
in36.txt AC 111 ms 13792 KB
1
in37.txt AC 107 ms 12720 KB
1
in38.txt AC 19 ms 764 KB
1
in39.txt AC 23 ms 720 KB
1
in40.txt AC 18 ms 676 KB
1
in41.txt AC 94 ms 13032 KB
1
in42.txt AC 106 ms 14456 KB
1
sample01.txt AC 20 ms 688 KB
1
sample02.txt AC 14 ms 640 KB
1