社区讨论

求助:代码为什么RE啊orzorz

P3071[USACO13JAN] Seating G参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi7dxkol
此快照首次捕获于
2025/11/20 20:05
4 个月前
此快照最后确认于
2025/11/20 20:05
4 个月前
查看原帖
RT
CPP
#include <bits/stdc++.h>
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define Mid ((l+r)>>1)
using namespace std;
const int N=500009;
int read(){
	char c;int num,f=1;
	while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0';
	while(c=getchar(), isdigit(c))num=num*10+c-'0';
	return f*num;
}
int qj[N*5],lq[N*5],rq[N*5],add[N*5];
void update(int rt,int len){
	qj[rt]=max(max(qj[lson(rt)],qj[rson(rt)]),rq[lson(rt)]+lq[rson(rt)]);
	lq[rt]=lq[lson(rt)]+(lq[lson(rt)]==len-len/2)*lq[rson(rt)];
	rq[rt]=rq[rson(rt)]+(rq[rson(rt)]==len/2)*rq[lson(rt)];
}
void pushdown(int rt,int len){
	if(add[rt]==-1||len==1)return ;
	qj[lson(rt)]=lq[lson(rt)]=rq[lson(rt)]=add[rt]*(len-len/2);
	qj[lson(rt)]=lq[lson(rt)]=rq[lson(rt)]=add[rt]*(len/2);
	add[lson(rt)]=add[rson(rt)]=add[rt];add[rt]=-1;
}
void build(int l,int r,int rt){
	qj[rt]=rq[rt]=lq[rt]=r-l+1;
	if(l==r)return ;
	build(l,Mid,lson(rt));
	build(Mid+1,r,rson(rt));
}
void modify(int l,int r,int L,int R,int rt,int x){
	if(L<=l&&r<=R){
		qj[rt]=lq[rt]=rq[rt]=x*(r-l+1);
		add[rt]=x;return ;
	}
	pushdown(rt,r-l+1);
	if(L<=Mid)modify(l,Mid,L,R,lson(rt),x);
	if(Mid<R) modify(Mid+1,r,L,R,rson(rt),x);
	update(rt,r-l+1);
}
int ask(int l,int r,int rt,int x){
	pushdown(rt,r-l+1);
	if(qj[rt]<x)return -1;
	if(qj[lson(rt)]>=x)return ask(l,Mid,lson(rt),x);
	else if(rq[lson(rt)]+lq[rson(rt)]>=x)return Mid-rq[lson(rt)]+1;
	else if(qj[rson(rt)]>=x)return ask(r,Mid,rson(rt),x);
}
int n,m,x,ans=0;
char c;
int main()
{
    memset(add,-1,sizeof(add));
    n=read();m=read();
	build(1,n,1);
	for(int i=1;i<=m;i++){
		cin>>c;
		if(c=='A'){
			x=read();
			int pos=ask(1,n,1,x);
			if(pos==-1)ans++;
			else modify(1,n,pos,pos+x-1,1,0);
		}else {
			int l=read(),r=read();
			modify(1,n,l,r,1,1);
		}
	}
	printf("%d\n",ans);
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...