結果

問題 No.2627 Unnatural Pitch
ユーザー kotatsugamekotatsugame
提出日時 2024-02-09 22:23:04
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 336 ms / 4,000 ms
コード長 1,421 bytes
コンパイル時間 723 ms
コンパイル使用メモリ 83,892 KB
実行使用メモリ 43,880 KB
最終ジャッジ日時 2024-02-09 22:23:10
合計ジャッジ時間 5,596 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 7 ms
10,932 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 213 ms
43,880 KB
testcase_05 AC 212 ms
43,880 KB
testcase_06 AC 180 ms
37,644 KB
testcase_07 AC 58 ms
36,920 KB
testcase_08 AC 86 ms
36,528 KB
testcase_09 AC 286 ms
43,880 KB
testcase_10 AC 304 ms
43,880 KB
testcase_11 AC 4 ms
6,676 KB
testcase_12 AC 4 ms
6,676 KB
testcase_13 AC 1 ms
6,676 KB
testcase_14 AC 5 ms
6,676 KB
testcase_15 AC 3 ms
6,676 KB
testcase_16 AC 295 ms
38,088 KB
testcase_17 AC 336 ms
43,624 KB
testcase_18 AC 265 ms
36,680 KB
testcase_19 AC 332 ms
40,008 KB
testcase_20 AC 94 ms
15,476 KB
testcase_21 AC 138 ms
23,984 KB
testcase_22 AC 245 ms
34,852 KB
testcase_23 AC 126 ms
23,036 KB
testcase_24 AC 162 ms
23,376 KB
testcase_25 AC 169 ms
24,840 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