专栏文章

题解：P11861 [CCC 2025 Senior] 写作业 / To-Do List

EELECTRODE_kaf
P11861题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipx2ggn
此快照首次捕获于
2025/12/03 19:21
3 个月前
此快照最后确认于
2025/12/03 19:21
3 个月前
查看原文
最优策略下，第一个开始做的任务一定是准时开始的。若我们决定第一个做任务 ii，那么总用时即为 si−1+∑j=intjs_i-1+\sum_{j=i}^{n}t_j，答案即为 max⁡(si−1+∑j=intj)\max(s_i-1+\sum_{j=i}^{n}t_j)。
用一颗线段树维护每一位开始的总和。插入新任务 (s,t)(s,t) 时，给 [1,s][1,s] 加上 tt。若目前它是第一个在时间 ss 开始的任务，则额外给 [s,s][s,s] 加上 s−1s-1。删除操作取反即可。
CPP
const ll N=1e6+10,mod=1e6+3;
ll Q,last,sgtr[N*4],lz[N*4],cnt[N];
vector<ll> ss,tt;

ll ls(ll p){
	return p*2;
}

ll rs(ll p){
	return p*2+1;
}

void pushdown(ll p){
	sgtr[ls(p)]+=lz[p];
	sgtr[rs(p)]+=lz[p];
	lz[ls(p)]+=lz[p];
	lz[rs(p)]+=lz[p];
	lz[p]=0;
}

void pushup(ll p){
	sgtr[p]=max(sgtr[ls(p)],sgtr[rs(p)]);
}

void upd(ll p,ll l,ll r,ll ql,ll qr,ll v){
	if(r<ql or l>qr) return;
	
	if(ql<=l and r<=qr){
		sgtr[p]+=v;
		lz[p]+=v;
	}else{
		if(lz[p]) pushdown(p);
		
		ll mid=(l+r)/2;
		upd(ls(p),l,mid,ql,qr,v);
		upd(rs(p),mid+1,r,ql,qr,v);
		pushup(p);
	}
}

int main(){
	ss.pb(-1);
	tt.pb(-1);
	cin>>Q;
	
	count(Q){
		char ty;
		cin>>ty;
		
		if(ty=='A'){
			ll s,t;
			cin>>s>>t;
			s=(s+last)%mod;
			t=(t+last)%mod;
//			cout<<"s="<<s<<",t="<<t<<'\n';
//			pause;
			ss.pb(s);
			tt.pb(t);
			upd(1,1,N,1,s,t);
			
			if(cnt[s]==0) upd(1,1,N,s,s,s-1);
				
			cnt[s]++;
		}else{
			ll x;
			cin>>x;
			x=(x+last)%mod;
//			cout<<"x="<<x<<'\n';
			upd(1,1,N,1,ss[x],-tt[x]);
			cnt[ss[x]]--;
			
			if(cnt[ss[x]]==0) upd(1,1,N,ss[x],ss[x],1-ss[x]);
		}
		
		last=sgtr[1];
		cout<<last<<'\n';
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...