結果

問題 No.924 紲星
ユーザー kotatsugamekotatsugame
提出日時 2019-11-08 23:34:15
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,970 ms / 4,000 ms
コード長 2,766 bytes
コンパイル時間 1,380 ms
コンパイル使用メモリ 97,908 KB
実行使用メモリ 21,128 KB
最終ジャッジ日時 2024-09-15 02:43:30
合計ジャッジ時間 33,511 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 8 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 10 ms
5,376 KB
testcase_06 AC 10 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 3,934 ms
19,672 KB
testcase_09 AC 3,930 ms
21,128 KB
testcase_10 AC 3,895 ms
20,768 KB
testcase_11 AC 3,970 ms
20,596 KB
testcase_12 AC 3,921 ms
20,672 KB
testcase_13 AC 1,971 ms
11,640 KB
testcase_14 AC 2,070 ms
10,292 KB
testcase_15 AC 1,819 ms
9,560 KB
testcase_16 AC 1,369 ms
15,416 KB
testcase_17 AC 3,097 ms
13,772 KB
testcase_18 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
#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()
{
	cin>>N>>Q;
	for(int i=0;i<N;i++)cin>>A[i];
	vector<pair<int,int> >Ai;
	for(int i=0;i<N;i++)Ai.push_back(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++)
	{
		cin>>L[i]>>R[i];
		L[i]--;
		l[i]=-1e9-1;
		r[i]=1e9+1;
	}
	for(int _=0;_<40;_++)
	{
		vector<pair<int,int> >T;
		for(int i=0;i<Q;i++)
		{
			int mid=(l[i]+r[i])/2;
			T.push_back(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++)cout<<ans[i]<<endl;
}
0