92pts WA on #2 求条
查看原帖
92pts WA on #2 求条
826774
Little_Fox_Fairy楼主2024/11/30 09:46
#include<bits/stdc++.h> 
#define int long long  
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#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)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; 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) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	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 false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	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 true; }
	inline void print(bool b) { putchar(b+48); }
	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 N=2e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;
struct node {
	int health,energy,attack,defense,collapse,idx,tim;
	bool operator == (const node &x) const {
		return x.health==health and x.energy==energy and x.attack==attack and x.defense==defense;
	}
}a[N],e[N],tmp1[N],tmp2[N];

int n,m,b[N],ans=-INF,f[N];
map<int,int> NATO;
int cnt;
namespace BIT {
	int t[N];
	inline int lowbit(int x) {return x&-x;}
	inline void update(int x,int val) {
		while (x<=n) {
			t[x]=max(val,t[x]);
			x+=lowbit(x);
		}
		return ;
	}
	inline int query(int x) {
		int ans=-INF;
		while (x) {
			ans=max(ans,t[x]);
			x-=lowbit(x);
		}
		return ans;
	}
	inline void clear(int x) {
		while (x<=n) {
			t[x]=-INF;
			x+=lowbit(x);
		} 
		return ;
	}
}using namespace BIT;
inline void cdqz(int l,int r) {
	if (l==r) return ;
	int mid=l+r>>1;
	cdqz(l,mid);
	for (int i=l;i<=r;i++) tmp2[i]=tmp1[i];
	stable_sort(tmp2+l,tmp2+mid+1,[](node x,node y){return (x.attack==y.attack?(x.defense==y.defense?x.collapse<y.collapse:x.defense<y.defense):x.attack<y.attack);});
	stable_sort(tmp2+mid+1,tmp2+r+1,[](node x,node y){return (x.attack==y.attack?(x.defense==y.defense?x.collapse<y.collapse:x.defense<y.defense):x.attack<y.attack);});
	int j=l;
	for (int i=mid+1;i<=r;i++) {
		while (tmp2[j].attack<=tmp2[i].attack and j<=mid) {
			if (tmp2[j].idx==1) update(tmp2[j].defense,f[tmp2[j].tim]);
			j++;
		}
		if (tmp2[i].idx==2) f[tmp2[i].tim]=max(f[tmp2[i].tim],query(tmp2[i].defense)+tmp2[i].collapse);
	}
	for (int i=l;i<j;i++) if(tmp2[i].idx==1) clear(tmp2[i].defense);
	cdqz(mid+1,r);
	return ;
}
inline void CDQ(int l,int r) {
	if (l==r) return ;
	int mid=l+r>>1;
	CDQ(l,mid);
	for (int i=l;i<=r;i++) tmp1[i]=e[i],tmp1[i].idx=(i<=mid?1:2);
	stable_sort(tmp1+l,tmp1+r+1,[](node x,node y){return (x.energy==y.energy?(x.attack==y.attack?(x.defense==y.defense?x.collapse<y.collapse:x.defense<y.defense):x.attack<y.attack):x.energy<y.energy);});
	cdqz(l,r);
	CDQ(mid+1,r);
	return ;
}
signed main() {
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>a[i].health>>a[i].energy>>a[i].attack>>a[i].defense;
		a[i].collapse=1;
		ans=max(ans,a[i].collapse);
	}
	stable_sort(a+1,a+n+1,[](node x,node y){return x.defense<y.defense;});
	for (int i=1;i<=n;i++) {
		if (!NATO[a[i].defense]) {
			NATO[a[i].defense]=++cnt;
			a[i].defense=NATO[a[i].defense];
		}
		else a[i].defense=NATO[a[i].defense];
	}
	for (int i=1;i<=n;i++) {
		int sum=a[i].collapse;
		ans=max(ans,sum);
		while (a[i]==a[i+1] and i+1<=n) {
			sum+=a[i+1].collapse;
			ans=max(ans,sum);
			i++;
		}++m;
		e[m]={a[i].health,a[i].energy,a[i].attack,a[i].defense,sum,0,m};
	}
	for (int i=1;i<=n;i++) t[i]=-INF;n=m;
	for (int i=1;i<=n;i++) f[i]=e[i].collapse;
	stable_sort(e+1,e+n+1,[](node x,node y){return x.health==y.health?(x.energy==y.energy?(x.attack==y.attack?(x.defense==y.defense?x.collapse<y.collapse:x.defense<y.defense):x.attack<y.attack):x.energy<y.energy):x.health<y.health;});
	CDQ(1,n);
	for (int i=1;i<=n;i++) ans=max(ans,f[i]);
	cout<<ans<<endl;
	return (0-0);
}

2024/11/30 09:46
加载中...