动态开点TLE警示后人
查看原帖
动态开点TLE警示后人
681809
BMWIsland楼主2024/5/27 23:06

inline int read(){int f=1,c=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}return f*c;}
inline void write(int x){if (x <0)putchar('-'),x= -x;if(x > 9)write(x / 10);putchar(x % 10 + '0');return;}

void pushup(int id){s[id]=s[ls[id]]+s[rs[id]];}
void pushdown(int id,int l,int r){
	if(lazy[id]==-1)return;
	if(!ls[id])ls[id]=++cnt;
	if(!rs[id])rs[id]=++cnt;
	int mid=((l+r)>>1);
	s[ls[id]]=lazy[id]*(mid-l+1);s[rs[id]]=lazy[id]*(r-mid);lazy[ls[id]]=lazy[rs[id]]=lazy[id];lazy[id]=-1;
}
void updata(int &id,int l,int r,int x,int y,int k){
	if(!id)id=++cnt;
	if(x<=l&&y>=r){s[id]=k*(r-l+1);lazy[id]=k;return;}
	int mid=((l+r)>>1);
	pushdown(id,l,r);
	if(x<=mid)updata(ls[id],l,mid,x,y,k);
	if(y>mid)updata(rs[id],mid+1,r,x,y,k);
	pushup(id);
}
int l,r,opt;
signed main(){
	memset(lazy,-1,sizeof lazy);
	n=read();q=read();
	while(q--){
		l=read(),r=read(),opt=read();
		if(opt==1)updata(base,1,n,l,r,1);
		else updata(base,1,n,l,r,0);
		write(n-s[base]);
		putchar('\n');
	}
}

这样直接TLE

#include<stdio.h>
#include<string.h>
using namespace std;

const int N = 15000005;
int base;
int cnt;
int n,q;


int ls[N];
int rs[N];
int s[N];
int lazy[N];
inline int read()
{
   int f=1,c=0;char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}
   return f*c;
}
inline void write(int x)
{
	if (x < 0) putchar('-'), x = -x;
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
	return;
}

inline void pushup(int id){
	s[id]=s[ls[id]]+s[rs[id]];
}
inline void pushdown(int id,int l,int r){
	if(lazy[id]==-1)return;
	if(!ls[id])ls[id]=++cnt;
	if(!rs[id])rs[id]=++cnt;
	int mid=((l+r)>>1);
	s[ls[id]]=lazy[id]*(mid-l+1);
	s[rs[id]]=lazy[id]*(r-mid);
	lazy[ls[id]]=lazy[rs[id]]=lazy[id];
	lazy[id]=-1;
}
inline void updata(int &id,int l,int r,int x,int y,int k){
	if(!id)id=++cnt;
	if(x<=l&&y>=r){
		s[id]=k*(r-l+1);
		lazy[id]=k;
		return;
	}
	int mid=((l+r)>>1);
	pushdown(id,l,r);
	if(x<=mid)updata(ls[id],l,mid,x,y,k);
	if(y>mid)updata(rs[id],mid+1,r,x,y,k);
	pushup(id);
}
int l,r,opt;
signed main(){
	// ios_base::sync_with_stdio(0);
	// cin.tie(nullptr);
	memset(lazy,-1,sizeof lazy);
	n=read();
	q=read();
	while(q--){
		l=read(),r=read(),opt=read();
		if(opt==1)updata(base,1,n,l,r,1);
		else updata(base,1,n,l,r,0);
		write(n-s[base]);
		putchar('\n');
	}
}

给函数全套上inline就过了,敬爱的CF同志,我认为这并不好笑

2024/5/27 23:06
加载中...