結果

問題 No.3367 Looks like a convolution
コンテスト
ユーザー kotatsugame
提出日時 2025-11-17 23:14:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,397 ms / 2,000 ms
コード長 2,070 bytes
コンパイル時間 1,502 ms
コンパイル使用メモリ 98,812 KB
実行使用メモリ 59,644 KB
最終ジャッジ日時 2025-11-17 23:14:23
合計ジャッジ時間 19,385 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<set>
#include<cassert>
#include<atcoder/lazysegtree>
using namespace std;
using dm=pair<long,int>;
dm opm(dm a,dm b){return min(a,b);}
dm em(){return make_pair((long)1e18,-1);}
dm mpm(long f,dm x)
{
	x.first+=f;
	return x;
}
long cmpm(long f,long g){return f+g;}
long idm(){return 0L;}
struct dat{
	long w;
	long s;
};
dat op(dat a,dat b){return a;}
dat e(){return(dat){};}
struct F{
	long a;
	long b;
	long c;
};
dat mp(F f,dat x)
{
	x.s+=f.c+f.b*x.w;
	x.w+=f.a;
	return x;
}
F cmp(F f,F g)
{
	g.c+=f.c+g.a*f.b;
	g.b+=f.b;
	g.a+=f.a;
	return g;
}
F id(){return(F){0L,0L,0L};}
int N,A[2<<17],B[2<<17];
long ans[2<<17];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	vector<pair<int,int> >vs(N+N);
	for(int i=0;i<N;i++)
	{
		cin>>A[i];
		vs[i]=make_pair(A[i],i);
	}
	for(int i=0;i<N;i++)
	{
		cin>>B[i];
		vs[N+i]=make_pair(B[i],N+i);
	}
	sort(vs.begin(),vs.end());
	vector<dm>initm(N);
	vector<dat>init(N);
	for(int k=0;k<N;k++)
	{
		initm[k].first=k+1;
		initm[k].second=k;
		init[k].w=k+1;
		init[k].s=0;
	}
	atcoder::lazy_segtree<dm,opm,em,long,mpm,cmpm,idm>segm(initm);
	atcoder::lazy_segtree<dat,op,e,F,mp,cmp,id>seg(init);
	seg.apply(0,N,(F){0,vs[0].first,0});
	set<int>a,b;
	a.insert(-1);
	a.insert(N);
	b.insert(-1);
	b.insert(N);
	for(int i=0;i<vs.size();i++)
	{
		int id=vs[i].second;
		if(id<N)
		{//A
			auto it=a.lower_bound(id);
			assert(it!=a.begin());
			assert(it!=a.end());
			int p=*prev(it);
			int nxt=*it;
			segm.apply(id,nxt,-(id-p));
			seg.apply(id,nxt,(F){-(id-p),0,0});
			a.insert(id);
		}
		else
		{//B
			id-=N;
			auto it=b.lower_bound(id);
			assert(it!=b.begin());
			assert(it!=b.end());
			int p=*prev(it);
			int nxt=*it;
			segm.apply(id,nxt,-(id-p));
			seg.apply(id,nxt,(F){-(id-p),0,0});
			b.insert(id);
		}
		while(true)
		{
			auto t=segm.all_prod();
			if(t.first>0)break;
			ans[t.second]=seg.get(t.second).s;
			segm.set(t.second,em());
		}
		if(i+1<vs.size())seg.apply(0,N,(F){0,vs[i+1].first-vs[i].first,0});
	}
	for(int i=0;i<N;i++)cout<<ans[i]<<(i+1==N?"\n":" ");
}
0