結果

問題 No.924 紲星
ユーザー 👑 testestest
提出日時 2020-12-10 20:06:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,011 bytes
コンパイル時間 2,057 ms
コンパイル使用メモリ 211,392 KB
最終ジャッジ日時 2025-01-16 21:34:17
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 1 WA * 10 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

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