結果

問題 No.2627 Unnatural Pitch
ユーザー kotatsugamekotatsugame
提出日時 2024-02-09 22:23:04
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 6 ms
10,892 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 218 ms
43,660 KB
testcase_05 AC 227 ms
43,656 KB
testcase_06 AC 188 ms
36,892 KB
testcase_07 AC 58 ms
36,268 KB
testcase_08 AC 87 ms
36,092 KB
testcase_09 AC 291 ms
43,704 KB
testcase_10 AC 296 ms
43,680 KB
testcase_11 AC 4 ms
6,816 KB
testcase_12 AC 5 ms
6,820 KB
testcase_13 AC 2 ms
6,820 KB
testcase_14 AC 4 ms
6,816 KB
testcase_15 AC 3 ms
6,816 KB
testcase_16 AC 296 ms
37,880 KB
testcase_17 AC 342 ms
43,472 KB
testcase_18 AC 274 ms
36,616 KB
testcase_19 AC 324 ms
39,668 KB
testcase_20 AC 99 ms
15,556 KB
testcase_21 AC 141 ms
23,820 KB
testcase_22 AC 252 ms
34,796 KB
testcase_23 AC 133 ms
22,904 KB
testcase_24 AC 163 ms
23,180 KB
testcase_25 AC 174 ms
24,692 KB
権限があれば一括ダウンロードができます

ソースコード

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