复杂度 Θ(NlogSlogD)
学校OJ的时限只有 1000ms,更过不了
码风有点抽象(学校神犇评价),勿喷
#include <bits/stdc++.h>
using namespace std;
namespace IO {
class FastIO {
private:
#define FS 1000000
#define gc() (A == B && (B = (A = FI) + fread(FI, 1, FS, stdin), A == B) ? EOF : *A++)
#define pc(c) (C ^ FS ? FO[C++] = c : (fwrite(FO, 1, C, stdout), FO[(C = 0)++] = c))
int C;
char *A, *B, FI[FS], FO[FS];
public:
FastIO() { A = B = FI; }
template <typename T> T rd() {
T res;
string typ = typeid(res).name();
if (typ == typeid(1).name() || typ == typeid(1ll).name()) {
long long a = 0, sgn = 1;
char c = gc();
for (; !isdigit(c); c = gc()) if (c == '-') sgn = -1;
for (; isdigit(c); c = gc()) a = (a << 3) + (a << 1) + c - '0';
return a * sgn;
}
if (typ == typeid('c').name()) return gc();
}
template <typename T> void wt(T a) {
string typ = typeid(a).name();
if (typ == typeid(1).name() || typ == typeid(1ll).name()) {
if (a < 0) pc('-'), a = -a;
int s[23], top = 0;
do { s[top++] = a % 10; } while (a /= 10);
while (top--) pc(s[top] + '0');
}
if (typ == typeid('c').name()) pc(a);
}
void clear() { fwrite(FO, 1, C, stdout), C = 0; }
} io;
#define rd io.rd
#define wt io.wt
} using namespace IO;
#define Abs(a) (a) < 0 ? -(a) : (a)
#define Max(a, b) (a) > (b) ? (a) : (b)
#define Min(a, b) (a) < (b) ? (a) : (b)
int d, s, n;
const int N = 10003;
struct Segy {
#define ls(x) (x) << 1
#define rs(x) (x) << 1 | 1
int tag[N], val[N];
void Modify(int u, int l, int r, int ql, int qr, int v) {
val[u] = Max(val[u], v);
if (l == ql && r == qr) return tag[u] = Max(tag[u], v), void();
int mid = l + r >> 1;
if (mid >= qr) Modify(ls(u), l, mid, ql, qr, v);
else if (mid + 1 <= ql) Modify(rs(u), mid + 1, r, ql, qr, v);
else Modify(ls(u), l, mid, ql, mid, v), Modify(rs(u), mid + 1, r, mid + 1, qr, v);
}
int Query(int u, int l, int r, int ql, int qr) {
if (l == ql && r == qr) return val[u];
int mid = l + r >> 1;
if (mid >= qr) return Max(Query(ls(u), l, mid, ql, qr), tag[u]);
else if (mid + 1 <= ql) return Max(Query(rs(u), mid + 1, r, ql, qr), tag[u]);
else return Max(Max(Query(ls(u), l, mid, ql, mid), Query(rs(u), mid + 1, r, mid + 1, qr)), tag[u]);
}
};
struct Segx {
#define ls(x) (x) << 1
#define rs(x) (x) << 1 | 1
Segy tag[N], val[N];
void Modify(int u, int l, int r, int ql, int qr, int _y0, int _y1, int v) {
val[u].Modify(1, 1, s, _y0, _y1, v);
if (l == ql && r == qr) return tag[u].Modify(1, 1, s, _y0, _y1, v), void();
int mid = (l + r) >> 1;
if (mid >= qr) Modify(ls(u), l, mid, ql, qr, _y0, _y1, v);
else if (mid + 1 <= ql) Modify(rs(u), mid + 1, r, ql, qr, _y0, _y1, v);
else
Modify(ls(u), l, mid, ql, mid, _y0, _y1, v), Modify(rs(u), mid + 1, r, mid + 1, qr, _y0, _y1, v);
}
int Query(int u, int l, int r, int ql, int qr, int _y0, int _y1) {
if (l == ql && r == qr) return val[u].Query(1, 1, s, _y0, _y1);
int mid = (l + r) >> 1, tmpv = tag[u].Query(1, 1, s, _y0, _y1);
if (mid >= qr) return Max(tmpv, Query(ls(u), l, mid, ql, qr, _y0, _y1));
else if (mid + 1 <= ql) return Max(tmpv, Query(rs(u), mid + 1, r, ql, qr, _y0, _y1));
else return Max(Max(Query(ls(u), l, mid, ql, mid, _y0, _y1), Query(rs(u), mid + 1, r, mid + 1, qr, _y0, _y1)), tmpv);
}
} sgt;
main() {
d = rd<int>(); s = rd<int>(); n = rd<int>();
for (int _d, _s, _w, _x, _y, val; n--; ) {
_d = rd<int>(), _s = rd<int>(), _w = rd<int>(), _x = rd<int>(), _y = rd<int>();
val = sgt.Query(1, 1, d, _x + 1, _x + _d, _y + 1, _y + _s);
sgt.Modify(1, 1, d, _x + 1, _x + _d, _y + 1, _y + _s, val + _w);
}
wt(sgt.Query(1, 1, d, 1, d, 1, s));
io.clear();
}