結果

問題 No.3411 Range Clamp Sum
コンテスト
ユーザー 👑 tails
提出日時 2025-12-18 03:34:57
言語 cLay
(20241019-1 + boost 1.89.0)
結果
AC  
実行時間 443 ms / 10,000 ms
コード長 1,224 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,099 ms
コンパイル使用メモリ 192,460 KB
実行使用メモリ 46,720 KB
最終ジャッジ日時 2025-12-18 03:35:09
合計ジャッジ時間 11,896 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#define BIN_SHIFT 11
#define BIN_N ((100000-1>>BIN_SHIFT)+1)
#define S_LIM 7000

int sum[BIN_N][1d5+2]{};
int num[BIN_N][1d5+2]{};
int@n,@q,@c[n];
rep(i,n){
	int j=i>>BIN_SHIFT;
	sum[j][c[i]+1]+=c[i];
	num[j][c[i]+1]+=1;
}
rep(j,BIN_N){
	rep(k,1d5+1){
		sum[j][k+1]+=sum[j][k];
		num[j][k+1]+=num[j][k];
	}
}

struct{int o,n;}s[BIN_N][S_LIM];
int sn[BIN_N]{},st=0;
rep(q){
	int@t;
	if(t==1){
		int@x--,@y;
		int j=x>>BIN_SHIFT;
		s[j][sn[j]++]={c[x],y};
		c[x]=y;
		if(++st==S_LIM){
			st=0;
			rep(j,BIN_N){
				int b[1d5+1]{};
				rep(i,sn[j]){
					b[s[j][i].o]-=1;
					b[s[j][i].n]+=1;
				}
				int zs=0;
				int zn=0;
				rep(k,1d5+1){
					sum[j][k+1]+=zs+=b[k]*k;
					num[j][k+1]+=zn+=b[k];
				}
				sn[j]=0;
			}
		}
	}else{
		int@(l--,r,a,b);
		ll z=0;
		if(l>>BIN_SHIFT==r>>BIN_SHIFT){
			while(l<r){
				z+=max(a,min(b,c[l]));
				++l;
			}
		}else{
			while(l&(1<<BIN_SHIFT)-1){
				z+=max(a,min(b,c[l]));
				++l;
			}
			while(r&(1<<BIN_SHIFT)-1){
				--r;
				z+=max(a,min(b,c[r]));
			}
			rep(j,l>>BIN_SHIFT,r>>BIN_SHIFT){
				z+=sum[j][b]-sum[j][a]+a*num[j][a]+b*(num[j][1d5+1]-num[j][b]);
				rep(i,sn[j]){
					z-=max(a,min(b,s[j][i].o));
					z+=max(a,min(b,s[j][i].n));
				}
			}
		}
		wt(z);
	}
}
0