結果

問題 No.2627 Unnatural Pitch
コンテスト
ユーザー kotatsugame
提出日時 2024-02-09 22:23:04
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 342 ms / 4,000 ms
コード長 1,421 bytes
コンパイル時間 752 ms
コンパイル使用メモリ 84,032 KB
実行使用メモリ 43,704 KB
最終ジャッジ日時 2024-09-28 15:37:27
合計ジャッジ時間 5,356 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cassert>
#include<atcoder/lazysegtree>
using namespace std;
long op(long a,long b){return min(a,b);}
long e(){return(long)1e18;}
long mp(long f,long x){return f+x;}
long id(){return 0L;}
int N,K;
long L,U,D;
long A[2<<17];
struct dat{
	long t;
	long b,sgn;
	long l,r;
	bool operator<(const dat&rhs)const{return t<rhs.t;}
};
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N>>K>>L>>U;
	D=U-L;
	vector<dat>OP;
	OP.reserve(2*N);
	for(int i=0;i<N;i++)
	{
		cin>>A[i];
		A[i]+=D;
		if(A[i]>D)
		{//pos
			long a=A[i]-D;
			long tl=0,tr=(a+K-1)/K;
			long b=a/K,sgn=-1;
			long al=0,ar=a%K;
			OP.push_back((dat){tl,b,sgn,al,ar});
			OP.push_back((dat){tr,b+sgn*(tr-tl),sgn*2,al,ar});
		}
		{//neg
			long tl=A[i]/K,tr=2e12;
			long b=0,sgn=1;
			long al=A[i]%K+1,ar=K;
			OP.push_back((dat){tl,b,sgn,al,ar});
			OP.push_back((dat){tr,b+sgn*(tr-tl),sgn*2,al,ar});
		}
	}
	atcoder::lazy_segtree<long,op,e,long,mp,mp,id>seg(vector<long>(K,0L));
	sort(OP.begin(),OP.end());
	long prvt=0;
	long B=0,SGN=0;
	long ans=1e18;
	for(dat d:OP)
	{
		if(prvt<d.t)
		{//[prvt,d.t)
			if(SGN>=0)ans=min(ans,B+seg.all_prod());
			else ans=min(ans,B+SGN*(d.t-prvt-1)+seg.all_prod());
			B+=SGN*(d.t-prvt);
			prvt=d.t;
		}
		if(abs(d.sgn)==1)
		{
			seg.apply(d.l,d.r,1L);
			B+=d.b;
			SGN+=d.sgn;
		}
		else
		{
			seg.apply(d.l,d.r,-1L);
			B-=d.b;
			SGN-=d.sgn/2;
		}
	}
	cout<<ans<<endl;
}
0