n 方五万求调 WA,不是 TLE
查看原帖
n 方五万求调 WA,不是 TLE
723238
wukaichen888楼主2023/11/15 17:22
#include <bits/stdc++.h>
using namespace std;
const int N=8e4+114,M=(N>>5)+14,p=998244353;
struct awa{
	int a,b,c,d,v,p;
	bool operator <(awa t) const{
		if(a!=t.a) return a<t.a;
		if(b!=t.b) return b<t.b;
		if(c!=t.c) return c<t.c;
		if(d!=t.d) return d<t.d;
		return p<t.p;
	}
}a[N];
bool cmp(pair<awa,int> x,pair<awa,int> y){
	if(x.first.b!=y.first.b) return x.first.b<y.first.b;
	if(x.first.a!=y.first.a) return x.first.a<y.first.a;
	if(x.first.c!=y.first.c) return x.first.c<y.first.c;
	if(x.first.d!=y.first.d) return x.first.d<y.first.d;
	return x.first.p<y.first.p;
}
bool cmp1(pair<awa,int> x,pair<awa,int> y){
	if(x.first.c!=y.first.c) return x.first.c<y.first.c;
	if(x.first.a!=y.first.a) return x.first.a<y.first.a;
	if(x.first.b!=y.first.b) return x.first.b<y.first.b;
	if(x.first.d!=y.first.d) return x.first.d<y.first.d;
	return x.first.p<y.first.p;
}
bool cmp2(pair<awa,int> x,pair<awa,int> y){
	if(x.first.d!=y.first.d) return x.first.d<y.first.d;
	if(x.first.a!=y.first.a) return x.first.a<y.first.a;
	if(x.first.b!=y.first.b) return x.first.b<y.first.b;
	if(x.first.c!=y.first.c) return x.first.c<y.first.c;
	return x.first.p<y.first.p;
}
int n,m;
long long f[N],g[N],f_[N>>3][256],g_[N>>3][256];
unsigned int h[2048][M],h1[2048][M],h2[2048][M];
pair<awa,int> b[N],b1[N],b2[N];
signed main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
//	for(int i=1;i<256;i+=2) g_[0][i]=1;
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n ;
	//	if(n>50000) return 0;
	for(int i=1;i<=n;++i) cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d , a[i].v=1,a[i].p=i;
	for(int i=1;i<=n;i++){
		 a[i].a +=1000000000;
		  a[i].b +=1000000000;
		   a[i].c +=1000000000;
		    a[i].d +=1000000000;
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i) b[i]=b1[i]=b2[i]=pair<awa,int>(a[i],i);
	sort(b+1,b+1+n,cmp);
	sort(b1+1,b1+1+n,cmp1);
	sort(b2+1,b2+1+n,cmp2);
	//	for(int i=1;i<=n;++i) cout << i << ": " << a[i].a << " " << a[i].b << " " << a[i].c << " " << a[i].d << " " << a[i].v << endl;
	for(int k=0;k<=(n>>11);++k){
		for(int j=1;j<=n>>5;++j) h[0][j]=h1[0][j]=h2[0][j]=0;
		for(int i=1,li=0,lp=0;i<=n;++i){
			int p=b[i].second;
			if(p>=(k<<11) && p<(k+1<<11)){
				p&=2047;
				memmove(h[p],h[lp],sizeof(h[0]));
				for(int j=li;j<i;++j){
					/*if(b[i].first.b>=b[j].first.b)*/ h[p][b[j].second>>5]|=1u<<(b[j].second&31);
					//					cout << "1: " << b[j].second << " " << (p|(k<<12)) << endl;
				}
				li=i,lp=p;
			}
		}
		for(int i=1,li=0,lp=0;i<=n;++i){
			int p=b1[i].second;
			if(p>=(k<<11) && p<(k+1<<11)){
				p&=2047;
				memmove(h1[p],h1[lp],sizeof(h1[0]));
				for(int j=li;j<i;++j){
					/*if(b1[i].first.c>=b1[j].first.c)*/ h1[p][b1[j].second>>5]|=1u<<(b1[j].second&31);
					//					cout << "2: " << b1[j].second << " " << (p|(k<<12)) << endl;
				}
				li=i,lp=p;
			}
		}
		for(int i=1,li=0,lp=0;i<=n;++i){
			int p=b2[i].second;
			if(p>=(k<<11) && p<(k+1<<11)){
				p&=2047;
				memmove(h2[p],h2[lp],sizeof(h2[0]));
				for(int j=li;j<i;++j){
					/*if(b2[i].first.d>=b2[j].first.d)*/ h2[p][b2[j].second>>5]|=1u<<(b2[j].second&31);
					//					cout << "3: " << b2[j].second << " " << (p|(k<<12)) << endl;
				}
				li=i,lp=p;
			}
		}
		for(int i=0;i<=2047;++i){
			for(int j=0;j<=n>>5;++j)
				h[i][j]&=h1[i][j]&h2[i][j];
		}
		for(int i=(k<<11),ii=0;i<(k+1<<11);++i,++ii){
			int t;
			long long* ff,*gg;
			for(int j=0;j<i;j+=32){
				t=h[ii][j>>5],ff=f_[j>>3];
				if(ff[(t>>0)&255|0]>f[i]) f[i]=ff[(t>>0)&255|0];
				if(ff[(t>>8)&255|256]>f[i]) f[i]=ff[(t>>8)&255|256];
				if(ff[(t>>16)&255|512]>f[i]) f[i]=ff[(t>>16)&255|512];
				if(ff[(t>>24)&255|768]>f[i]) f[i]=ff[(t>>24)&255|768];
			}
			f[i]+=a[i].v;
			//			if(i<=n) cout << i << " " << f[i] << " " << g[i] << endl;
			//			cout << g[0] << endl;
			for(int j=0;j<=255;++j){
				if((j>>(i&7))&1){
					if(f[i]>f_[i>>3][j]) f_[i>>3][j]=f[i],g_[i>>3][j]=0;
				}
			}
			for(int j=0;j<=255;++j){
				if((j>>(i&7))&1 && f[i]==f_[i>>3][j]) g_[i>>3][j]+=g[i];
			}
		}
	}
	long long ans=*max_element(f+1,f+1+n);
	cout << ans  << endl;
	return 0;
}
2023/11/15 17:22
加载中...