TLE,求卡
查看原帖
TLE,求卡
1198768
qazsedcrfvgyhnujijn楼主2024/4/29 22:47

复杂度 Θ(Nlog⁡Slog⁡D)\Theta(N\log S \log D)
学校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();
}
2024/4/29 22:47
加载中...