結果

問題 No.1270 Range Arrange Query
ユーザー kotatsugamekotatsugame
提出日時 2020-10-24 02:59:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,400 bytes
コンパイル時間 1,349 ms
コンパイル使用メモリ 96,624 KB
実行使用メモリ 8,372 KB
最終ジャッジ日時 2023-09-28 20:03:25
合計ジャッジ時間 10,153 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 3 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 6 ms
4,380 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
a.cpp:12:1: 警告: ISO C++ では型の無い ‘main’ の宣言を禁止しています [-Wreturn-type]

ソースコード

diff # 

#line 1 "a.cpp"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#line 2 "/home/kotatsugame/library/datastructure/lazysegtree.cpp"
#include<functional>
template<typename T>
struct lazysegtree{
	using F=function<T(T,T)>;
	using G=function<T(T,T,int,int)>;
	const F calcfn,lazycalcfn;
	const G updatefn;
	int n;
	T defvalue;
	vector<T>dat,lazy;
	vector<bool>lazyflag;
	lazysegtree(int n_=0,T defvalue_=0,
		const F calcfn_=[](T a,T b){return a+b;},
		const F lazycalcfn_=[](T a,T b){return a+b;},
		const G updatefn_=[](T a,T b,int l,int r){return a+b*(r-l);}
	):defvalue(defvalue_),
		calcfn(calcfn_),lazycalcfn(lazycalcfn_),updatefn(updatefn_)
	{
		n=1;
		while(n<n_)n<<=1;
		dat.assign(2*n-1,defvalue);
		lazy.assign(2*n-1,T());
		lazyflag.assign(2*n-1,false);
	}
	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[2*i+1],dat[2*i+2]);
	}
	void eval(int i,int l,int r)
	{
		if(lazyflag[i])
		{
			dat[i]=updatefn(dat[i],lazy[i],l,r);
			if(r-l>1)
			{
				lazy[2*i+1]=lazyflag[2*i+1]?lazycalcfn(lazy[2*i+1],lazy[i]):lazy[i];
				lazy[2*i+2]=lazyflag[2*i+2]?lazycalcfn(lazy[2*i+2],lazy[i]):lazy[i];
				lazyflag[2*i+1]=lazyflag[2*i+2]=true;
			}
			lazyflag[i]=false;
		}
	}
	void update(int a,int b,T x,int k=0,int l=0,int r=-1)//[a,b)
	{
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return;
		else if(a<=l&&r<=b)
		{
			lazy[k]=lazyflag[k]?lazycalcfn(lazy[k],x):x;
			lazyflag[k]=true;
			eval(k,l,r);
		}
		else
		{
			update(a,b,x,2*k+1,l,(l+r)/2);
			update(a,b,x,2*k+2,(l+r)/2,r);
			dat[k]=calcfn(dat[2*k+1],dat[2*k+2]);
		}
	}
	T query(int a,int b,int k=0,int l=0,int r=-1)//[a,b)
	{
		if(r<0)r=n;
		eval(k,l,r);
		if(b<=l||r<=a)return defvalue;
		else if(a<=l&&r<=b)return dat[k];
		else return calcfn(
			query(a,b,2*k+1,l,(l+r)/2),
			query(a,b,2*k+2,(l+r)/2,r)
		);
	}
};
#line 1 "/home/kotatsugame/library/datastructure/BIT.cpp"
//1-indexed
#line 3 "/home/kotatsugame/library/datastructure/BIT.cpp"
template<typename T>
struct BIT{
	int n;
	vector<T>bit;
	BIT(int n_=0):n(n_),bit(n_+1){}
	T sum(int i)
	{
		T ans=0;
		for(;i>0;i-=i&-i)ans+=bit[i];
		return ans;
	}
	void add(int i,T a)
	{
		if(i==0)return;
		for(;i<=n;i+=i&-i)bit[i]+=a;
	}
	int lower_bound(T k)//k<=sum(ret)
	{
		if(k<=0)return 0;
		int ret=0,i=1;
		while((i<<1)<=n)i<<=1;
		for(;i;i>>=1)
			if(ret+i<=n&&bit[ret+i]<k)k-=bit[ret+=i];
		return ret+1;
	}
};
#line 7 "a.cpp"
int N,Q;
int A[20000];
vector<pair<int,int> >G[20000];
int ans[20000];
int cnt[20002];
main()
{
	cin>>N>>Q;
	for(int i=0;i<N;i++)
	{
		cin>>A[i];
		A[i]--;
	}
	for(int i=0;i<Q;i++)
	{
		int l,r;cin>>l>>r;
		l--;
		G[l].push_back(make_pair(r,i));
	}
	int L=0;
	BIT<int>cntsum(N);
	for(int l=0;l<N;l++)
	{
		sort(G[l].begin(),G[l].end());
		lazysegtree<int>P(N,(int)1e9,
		[](int a,int b){return a<b?a:b;},
		[](int a,int b){return a+b;},
		[](int a,int b,int l,int r){return a+b;});
		P.copy(vector<int>(N,0));
		for(int i=0;i<N;i++)P.update(i,N,-cnt[i]);
		int id=N;
		int all=L;
		BIT<int>R(N);
		for(int i=G[l].size();i--;)
		{
			while(id>G[l][i].first)
			{
				id--;
				P.update(A[id]+1,N,1);
				all+=cntsum.sum(N-A[id]-1);
				all+=R.sum(A[id]);
				R.add(A[id]+1,1);
			}
			ans[G[l][i].second]=(l+P.query(0,N))*(id-l)+all;
		}
		L+=cntsum.sum(N-A[l]-1);
		cntsum.add(N-A[l],1);
		cnt[A[l]]++;
	}
	for(int i=0;i<Q;i++)cout<<ans[i]<<endl;
}
0