結果

問題 No.924 紲星
コンテスト
ユーザー kotatsugame
提出日時 2019-11-08 23:37:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,427 ms / 4,000 ms
コード長 2,780 bytes
コンパイル時間 1,002 ms
コンパイル使用メモリ 78,000 KB
実行使用メモリ 19,284 KB
最終ジャッジ日時 2024-09-15 02:45:15
合計ジャッジ時間 29,236 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main()
      | ^~~~

ソースコード

diff # 

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#include<vector>
#include<functional>
#include<limits>
template<typename T>
struct segtree{
	function<T(T,T)>calcfn,updatefn;
	int n;
	T defvalue;
	vector<T>dat;
	segtree(int n_=0,T defvalue_=numeric_limits<T>::max(),
		function<T(T,T)>calcfn_=[](T a,T b){return a<b?a:b;},
		function<T(T,T)>updatefn_=[](T a,T b){return b;}
	):defvalue(defvalue_),calcfn(calcfn_),updatefn(updatefn_)
	{
		n=1;
		while(n<n_)n<<=1;
		dat.assign(2*n-1,defvalue);
	}
	void copy(const vector<T>&v)
	{
		for(int i=0;i<v.size();i++)dat[i+n-1]=v[i];
		for(int i=n-2;i>=0;i--)dat[i]=calcfn(dat[i*2+1],dat[i*2+2]);
	}
	void update(int i,T a)
	{
		i+=n-1;
		dat[i]=updatefn(dat[i],a);
		while(i>0)
		{
			i=(i-1)/2;
			dat[i]=calcfn(dat[2*i+1],dat[2*i+2]);
		}
	}
	T query(int a,int b)//[a,b)
	{
		int L=(a<0?0:a>n?n:a)+n-1;
		int R=(b<0?0:b>n?n:b)+n-1;
		T lret=defvalue,rret=defvalue;
		for(;L<R;L>>=1,R>>=1)
		{
			if(!(L&1))lret=calcfn(lret,dat[L]);
			if(!(R&1))rret=calcfn(dat[--R],rret);
		}
		return calcfn(lret,rret);
	}
};
int N,Q;
int A[2<<17];
int L[2<<17],R[2<<17];
int l[2<<17],r[2<<17];
long ans[2<<17];
main()
{
	scanf("%d%d",&N,&Q);
	for(int i=0;i<N;i++)scanf("%d",A+i);
	vector<pair<int,int> >Ai(N);
	for(int i=0;i<N;i++)Ai[i]=make_pair(A[i],~i);
	vector<pair<int,int> >Qi(Ai.begin(),Ai.end());
	sort(Ai.begin(),Ai.end());
	for(int i=0;i<Q;i++)
	{
		scanf("%d%d",L+i,R+i);
		L[i]--;
		l[i]=-1e9-1;
		r[i]=1e9+1;
	}
	for(int _=0;_<40;_++)
	{
		vector<pair<int,int> >T(Q);
		for(int i=0;i<Q;i++)
		{
			int mid=(l[i]+r[i])/2;
			T[i]=make_pair(mid,i);
		}
		sort(T.begin(),T.end());
		segtree<int>cnt(N,0,[](int a,int b){return a+b;},[](int a,int b){return b;});
		int id=0;
		for(int i=0;i<N;i++)
		{
			while(id<Q&&Ai[i].first>T[id].first)
			{
				int idd=T[id].second;
				if(cnt.query(L[idd],R[idd])>=(R[idd]-L[idd]+1)/2)r[idd]=T[id].first;
				else l[idd]=T[id].first;
				id++;
			}
			cnt.update(~Ai[i].second,1);
		}
		while(id<Q)
		{
			int idd=T[id].second;
			if(cnt.query(L[idd],R[idd])>=(R[idd]-L[idd])/2)r[idd]=T[id].first;
			else l[idd]=T[id].first;
			id++;
		}
	}
	for(int i=0;i<Q;i++)
	{
		Qi.push_back(make_pair(r[i],i));
	}
	sort(Qi.begin(),Qi.end());
	segtree<long>SUM(N,0,[](long a,long b){return a+b;},[](long a,long b){return b;});
	SUM.copy(vector<long>(A,A+N));
	segtree<int>neg(N,0,[](int a,int b){return a+b;},[](int a,int b){return b;});
	for(pair<int,int>p:Qi)
	{
		int id=p.second;
		int X=p.first;
		if(id<0)
		{
			id=~id;
			SUM.update(id,-X);
			neg.update(id,1);
		}
		else
		{
			int w=R[id]-L[id];
			long now=SUM.query(L[id],R[id]);
			int cnt=neg.query(L[id],R[id]);
			now+=(long)X*cnt-(long)X*(w-cnt);
			ans[id]=now;
		}
	}
	for(int i=0;i<Q;i++)printf("%ld\n",ans[i]);
}
0