結果

問題 No.3761 Moonlit Battle
コンテスト
ユーザー kotatsugame
提出日時 2026-10-10 00:38:02
言語 C++14
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 134 ms / 2,000 ms
+ 244µs
コード長 1,688 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 704 ms
コンパイル使用メモリ 112,580 KB
実行使用メモリ 28,620 KB
最終ジャッジ日時 2026-10-10 00:38:08
合計ジャッジ時間 4,335 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:40:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   40 |         for(auto[A,B]:AB)
      |                 ^

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
#include<atcoder/segtree>
using namespace std;
struct dat{
	long ALL,MIN;
};
dat op(dat a,dat b)
{
	a.MIN=min(a.MIN,a.ALL+b.MIN);
	a.ALL+=b.ALL;
	return a;
}
dat e(){return(dat){0L,0L};}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,D;cin>>N>>D;
	vector<int>vs;
	vs.reserve(N+2);
	vs.push_back(0);
	vs.push_back(D);
	vector<pair<int,int> >AB(N);
	__int128 cur=0;
	for(int i=0;i<N;i++)
	{
		int A,B;cin>>A>>B;
		cur+=(B+D-1)/D*(long)A;
		vs.push_back(B%D);
		AB[i]=make_pair(A,B);
	}
	AB.push_back(make_pair(0,D));
	sort(vs.begin(),vs.end());
	vs.erase(unique(vs.begin(),vs.end()),vs.end());
	vector<dat>init(vs.size()-1,e());
	for(int i=0;i<init.size();i++)init[i].ALL+=vs[i+1]-vs[i];
	for(auto[A,B]:AB)
	{
		int i=lower_bound(vs.begin(),vs.end(),B%D==0?D:B%D)-vs.begin();
		assert(i>0);
		init[i-1].ALL-=A;
	}
	for(dat&x:init)if(x.ALL<0)x.MIN=x.ALL;
	atcoder::segtree<dat,op,e>seg(init);
	sort(AB.begin(),AB.end(),[](pair<int,int>l,pair<int,int>r){return l.second<r.second;});
	__int128 ans=cur;
	for(int i=0;i<AB.size();)
	{
		int B=AB[i].second;
		int q=(B+D-1)/D;
		ans=min(ans,cur+seg.all_prod().MIN);
		cur+=seg.all_prod().ALL;
		while(i<AB.size()&&(AB[i].second+D-1)/D==q)
		{
			int b=AB[i].second;
			int id=lower_bound(vs.begin(),vs.end(),b%D==0?D:b%D)-vs.begin();
			assert(id>0);
			init[id-1].ALL+=AB[i++].first;
			init[id-1].MIN=min(0L,init[id-1].ALL);
			seg.set(id-1,init[id-1]);
		}
		ans=min(ans,cur+seg.all_prod().MIN);
		if(i<AB.size())
		{
			int nq=(AB[i].second+D-1)/D;
			assert(q<nq);
			cur+=seg.all_prod().ALL*(__int128)(nq-q-1);
		}
	}
	cout<<(long)ans<<endl;
}
0