20分性感代码在线求调
查看原帖
20分性感代码在线求调
550775
rsy_楼主2024/7/4 14:05
#include <bits/stdc++.h>
#define lb(x) (x&-x)
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define int long long

using namespace std;
using i64 = long long;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
void chmin(int &x, int c) {
	x = min(x, c);
}
void chmax(int &x, int c) {
	x = max(x, c);
}

namespace fast_IO {
#define IOSIZE 100000
	int precision = 3, POW[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
	#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
	#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
	#define isdigit(ch) (ch>47&&ch<58)
	#define isspace(ch) (ch<33)
#endif
	template<typename T>inline T read() {
		T s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) && (ch != EOF))if (ch == 45)w = -1;
		if (ch == EOF)return 0;
		while (isdigit(ch))s = s * 10 + ch - 48, ch = getchar();
		return s * w;
	} template<typename T>inline bool read(T&s) {
		s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) && (ch != EOF))if (ch == 45)w = -1;
		if (ch == EOF)return 0;
		while (isdigit(ch))s = s * 10 + ch - 48, ch = getchar();
		return s *= w, 1;
	} inline bool read(char&s) {
		while (s = getchar(), isspace(s));
		return 1;
	} inline bool read(char*s) {
		char ch;
		while (ch = getchar(), isspace(ch));
		if (ch == EOF)return 0;
		while (!isspace(ch))*s++ = ch, ch = getchar();
		*s = '\000';
		return 1;
	} template<typename T>inline void print(T x) {
		if (x < 0)putchar(45), x = -x;
		if (x > 9)print(x / 10);
		putchar(x % 10 + 48);
	} inline void print(char x) {
		putchar(x);
	} inline void print(char*x) {
		while (*x)putchar(*x++);
	} inline void print(const char*x) {
		for (int i = 0; x[i]; i++)putchar(x[i]);
	} inline bool read(std::string&s) {
		s = "";
		char ch;
		while (ch = getchar(), isspace(ch));
		if (ch == EOF)return 0;
		while (!isspace(ch))s += ch, ch = getchar();
		return 1;
	} inline void print(std::string x) {
		for (int i = 0, n = x.size(); i < n; i++)putchar(x[i]);
	} inline bool read(bool&b) {
		char ch;
		while (ch = getchar(), isspace(ch));
		b = ch ^ 48;
		return 1;
	} inline void print(bool b) {
		putchar(b + 48);
	} inline bool read(double&x) {
		int a = 0, b = 0;
		char ch = getchar();
		bool f = 0;
		while (ch < 48 || ch > 57) {
			if (ch == 45)f = 1;
			ch = getchar();
		}
		while (47 < ch && ch < 58) {
			a = (a << 1) + (a << 3) + (ch ^ 48);
			ch = getchar();
		}
		if (ch != 46) {
			x = f ? -a : a;
			return 1;
		}
		ch = getchar();
		while (47 < ch && ch < 58) {
			b = (b << 1) + (b << 3) + (ch ^ 48), ch = getchar();
		}
		x = b;
		while (x > 1)x /= 10;
		x = f ? -a - x : a + x;
		return 1;
	} inline void print(double x) {
		if (x < 0) {
			putchar(45), x = -x;
		}
		x = round((long double)x * POW[precision]) / POW[precision], print((long long)x), putchar(46), x -= (long long)(x);
		for (int i = 1; i <= precision; i++)x *= 10, putchar(x + 48), x -= (int)x;
	} template<typename T, typename...T1>inline int read(T& a, T1&...other) {
		return read(a) + read(other...);
	} template<typename T, typename...T1>inline void print(T a, T1...other) {
		print(a), print(other...);
	} struct Fast_IO {
		~Fast_IO() {
			fwrite(obuf, p3 - obuf, 1, stdout);
		}
	} io;
	template<typename T>Fast_IO& operator>>(Fast_IO&io, T&b) {
		return read(b), io;
	} template<typename T>Fast_IO& operator<<(Fast_IO&io, T b) {
		return print(b), io;
	}
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
const int maxn = 3e5 + 10, mod = 998244353;
int n, cnt; 
struct qwq {
	int a, b, c, d, w, res; bool f;
}a[maxn];
int c[maxn];
void upd (int x, int v) {
	for (int i = x; i <= cnt; i += (i & -i))
		c[i] = max (c[i], v);
}
int sum (int x) {
	int mx = 0;
	for (int i = x; i > 0; i -= (i & -i))
		mx = max (mx, c[i]);
	return mx; 
}
void clear (int x) {
	for (int i = x; i <= cnt; i += (i & -i))
		c[i] = 0;
}
void cqd2 (int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	cqd2 (l, mid);
	sort (a + l, a + mid + 1, [](qwq i, qwq j){
		if(i.c != j.c) return i.c < j.c;
		return i.d < j.d;
	});
	sort (a + mid + 1, a + r + 1, [](qwq i, qwq j){
		if (i.c != j.c) return i.c < j.c;
		return i.d < j.d;
	});
	for (int i = l, j = mid + 1; j <= r; j ++ ) {
		while (i <= mid && a[i].c <= a[j].c) {
			if (a[i].f) {
				upd (a[i].d, a[i].res);
			}
			i ++ ;
		}
		if (!a[j].f) {
			a[j].res = max (a[j].res, sum(a[j].d) + a[j].w);
		}
	}
	for (int j = l; j <= mid; j ++ ) if (!a[j].f) clear(a[j].d);
	sort (a + l, a + r + 1, [](qwq i, qwq j){
		if (i.b != j.b) return i.b < j.b;
		if (i.c != j.c) return i.c < j.c;
		return i.d < j.d;
	});
	cqd2 (mid + 1, r);
}
void cqd1 (int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	cqd1 (l, mid);
	for (int i = l; i <= mid; i ++ ) a[i].f = 1;
	for (int i = mid + 1; i <= r; i ++ ) a[i].f = 0;
	sort (a + l, a + r + 1, [](qwq i, qwq j){
		if (i.b != j.b) return i.b < j.b;
		if (i.c != j.c) return i.c < j.c;
		return i.d < j.d; 
	});
	cqd2 (l, r);
	sort (a + l, a + r + 1, [](qwq i, qwq j){
		if (i.a != j.a) return i.a < j.a;
		if (i.b != j.b) return i.b < j.b;
		if (i.c != j.c) return i.c < j.c;
		return i.d < j.d; 
	});
	cqd1 (mid + 1, r);
}
int b[maxn];

void solve() {
	cin >> n;
	bool F = 0;
	for (int i = 1; i <= n; i ++ ) {
		cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d, a[i].w = 1;
		b[++ cnt] = a[i].d, a[i].res = a[i].w;
	}
	sort (b + 1, b + 1 + cnt);
	cnt = unique (b + 1, b + 1 + cnt) - b - 1;
	for (int i = 1; i <= n; i ++ ) {
		a[i].d = lower_bound(b + 1, b + 1 + cnt, a[i].d) - b;
	} 
	sort (a + 1, a + 1 + n, [](qwq i, qwq j){
		if (i.a != j.a) return i.a < j.a;
		if (i.b != j.b) return i.b < j.b;
		if (i.c != j.c) return i.c < j.c;
		return i.d < j.d;
	});
	cqd1 (1, n);
	int res = -LLONG_MAX / 2;
	for (int i = 1; i <= n; i ++ ) {
		res = max (res, a[i].w);
	}
	for (int i = 1; i <= n; i ++ ) {
		res = max (res, a[i].res);
	}
	cout << res << '\n';
}

signed main() {
	int T = 1;
	while (T--)solve();
	return 0;
}

这个帖子里面的东西我写的貌似是对的。

2024/7/4 14:05
加载中...