結果

問題 No.924 紲星
ユーザー testestesttestestest
提出日時 2020-12-10 20:06:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,011 bytes
コンパイル時間 2,578 ms
コンパイル使用メモリ 220,168 KB
実行使用メモリ 13,764 KB
最終ジャッジ日時 2023-10-20 00:51:04
合計ジャッジ時間 8,796 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
priority_queue<int> lin,lout;
priority_queue<int,vector<int>,greater<int>> rin,rout;
long long ls,rs;

//l==rかl==r+1
void balance(){
	while(lin.size()-lout.size()<rin.size()-rout.size()){
		//rからlへ
		while(rin.size()&&rout.size()&&rin.top()==rout.top()){
			rin.pop();
			rout.pop();
		}
		int temp=rin.top();rin.pop();
		rs-=temp;
		lin.push(temp);
		ls+=temp;
	}
	
	while(lin.size()-lout.size()>rin.size()-rout.size()+1){
		//lからrへ
		while(lin.size()&&lout.size()&&lin.top()==lout.top()){
			lin.pop();
			lout.pop();
		}
		int temp=lin.top();lin.pop();
		ls-=temp;
		rin.push(temp);
		rs+=temp;
	}
}

void push(int v){
	if(lin.size()==0||v<=lin.top()){
		lin.push(v);
		ls+=v;
	}else{
		rin.push(v);
		rs+=v;
	}
	balance();
}

void pop(int v){
	if(v<=lin.top()){
		lout.push(v);
		ls-=v;
	}else{
		rout.push(v);
		rs-=v;
	}
	balance();
}

long long query(){
	long long x=lin.top();
	int lcnt=lin.size()-lout.size();
	int rcnt=rin.size()-rout.size();
	
	return (x*lcnt-ls)+(rs-x*rcnt);
}

void del(){
	priority_queue<int> lin2,lout2;
	priority_queue<int,vector<int>,greater<int>> rin2,rout2;
	lin=lin2;lout=lout2;
	rin=rin2;rout=rout2;
	ls=0;rs=0;
}

const int len=500;

int cmp(const tuple<int,int,int>p, const tuple<int,int,int>q){
	if(get<0>(p)/len < get<0>(q)/len)return true;
	if(get<0>(p)/len > get<0>(q)/len)return false;
	if(get<1>(p) < get<1>(q))return true;
	if(get<1>(p) > get<1>(q))return false;
	return false;
}

int main(){
	int n, q;
	cin >> n >> q;
	
	vector<int>a(n);
	for(auto& e:a)cin >> e;
	vector<tuple<int,int,int>>b(q);
	for(int i=0;i<q;i++){
		int l, r;
		cin >> l >> r;
		b[i]=make_tuple(l-1,r,i);
	}
	sort(b.begin(), b.end(), cmp);
	
	vector<long long>ans(q);
	int l=0,r=0,val=-1;
	for(int ii=0;ii<q;ii++){
		auto [nl,nr,i]=b[ii];
		if(val!=nl/len){
			del();
			l=r=nl;
			val=nl/len;
		}
		while(r<nr)push(a[r++]);
		while(l<nl)pop(a[l++]);
		while(l>nl)push(a[--l]);
		ans[i]=query();
	}
	for(auto v:ans)cout<< v<<endl;
}
0