社区讨论
求助:代码为什么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 条回复,欢迎继续交流。
正在加载回复...