#591695 (C++17) No.924 紲星

• 問題: No.924 紲星
• ユーザー: 👑 testestest
• 提出日時: 2020-12-10 20:06:10
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 2,011 bytes
• コンパイル時間: 2,250 ms
• コンパイル使用メモリ: 220,636 KB
• 実行使用メモリ: 16,280 KB
• 最終ジャッジ日時: 2024-09-19 20:40:18
• 合計ジャッジ時間: 8,471 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 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	--	-

ソースコード

#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;
}