Submission #544231

#	Time	Username	Problem	Language	Result	Execution time	Memory
544231		Antekb	Fire (JOI20_ho_t5)	C++14	100 / 100	767 ms	29972 KiB

ho_t5

#include<bits/stdc++.h>
//#pragma GCC optimize("trapv")
#define st first
#define nd second
using namespace std;
using ll = long long;
const int N=1<<18;
int tab[N], L[N], R[N];
int pr[N], le[N];
int ile[N+N];
ll sum[N+N];
set<int> S;
int n;
/*int pra(int i){
	//cout<<i<<" "<<ile[n+N+1]<<endl;
	//assert(ile[N+n+1]);
	for(i+=N; i>0; i/=2){
		if((i&1)==0 && ile[i+1]){
			i++;
			while(i<N){
				if(ile[i+i])i=i+i;
				else i=i+i+1;
			}
			//cout<<"? "<<i-N<<endl;
			return i-N;
		}
	}
	assert(false);
	return 0;
}*/
/*int lew(int i){
	for(i+=N; i>0; i/=2){
		if((i&1) && ile[i-1]){
			i--;
			while(i<N){
				if(ile[i+i+1])i=i+i+1;
				else i=i+i;
			}
			//cout<<"? "<<i-N<<endl;
			return i-N;
		}
	}
	assert(false);
	return 0;
}*/
int lew(int i){
	if(le[i]==i)return i;
	return le[i]=lew(le[i]);
}
int pra(int i){
	if(pr[i]==i)return i;
	return pr[i]=pra(pr[i]);
}
void upd(int i){
	if(i==0 || i==n+1)return;
	//cout<<i<<"u"<<endl;
	if(S.find(i)!=S.end())S.erase(S.find(i));
	//cout<<i<<"a"<<lew(i)<<" "<<tab[lew(i)]<<" "<<tab[i]<<"\n";
	L[i]=(tab[lew(i-1)]>tab[i]);
	R[i]=(tab[pra(i+1)]<tab[i]);
	if(L[i]^R[i]){
		S.insert(i);
	}
	//cout<<i<<"u"<<endl;
}
void usun(int i){
	//cout<<"- "<<i<<endl;
	int ii=i;
	for(i+=N; i>0; i>>=1){
		sum[i]-=tab[ii];
		ile[i]--;
		assert(ile[i]>=0);
	}
	if(ile[ii+N]==0){
		S.erase(S.find(ii));
		le[ii]=ii-1;
		pr[ii]=ii+1;
		upd(lew(ii-1));
		upd(pra(ii+1));
	}
}
void dodaj(int i){
	int ii=i;
	for(i+=N; i>0; i>>=1){
		sum[i]+=tab[ii];
		ile[i]++;
	}
}
ll quer(int k){
	ll ans=0;
	int v=1;
	while(v<N){
		if(ile[v+v]<=k){
			k-=ile[v+v];
			ans+=sum[v+v];
			v=v+v+1;
		}
		else v=v+v;
	}
	assert(k<=ile[v]);
	if(k)ans+=k*1ll*tab[v-N];
	return ans;
}
int main(){
	int q;
	cin>>n>>q;
	tab[0]=0;
	ile[N]=1;
	for(int i=0; i<=n+1; i++)le[i]=pr[i]=i;
	for(int i=1; i<=n; i++){
		cin>>tab[i];
		ile[N+i]=1;
		sum[N+i]=tab[i];
	}
	tab[n+1]=1e9+5;
	ile[n+1+N]=1;
	for(int i=N-1; i>0; i--){
		ile[i]=ile[i+i]+ile[i+i+1];
		sum[i]=sum[i+i]+sum[i+i+1];
	}
	for(int i=1; i<=n; i++){
		upd(i);
		//cout<<L[i]<<" "<<R[i]<<"\n";
	}
	vector<pair<pair<int, int>, pair<int, int> > > Q(q);
	for(int i=0; i<q; i++){
		Q[i].st.nd=i;
		cin>>Q[i].st.st>>Q[i].nd.st>>Q[i].nd.nd;
		Q[i].nd.nd++;
	}
	vector<ll> ans(q);
	sort(Q.begin(), Q.end());
	int wsk=0;
	//assert(S.find(0)==S.end());
	for(int t=1; t<=n; t++){
		//cout<<t<<"aaa"<<endl;
		vector<int> V, V2;
		for(auto it=S.begin(); it!=S.end(); it++){
			//cout<<*it<<"\n";
			//V.push_back(*it);
			if(L[*it])V.push_back(*it);
			else V2.push_back(*it);
		}
		/*for(int i:V)
		{
			//assert(i!=0);
			if(L[i]){
				//cout<<"- "<<i<<endl;
				usun(i);
			}
			else{
				//cout<<"+ "<<i<<endl;
				dodaj(i);
			}
		}*/
		for(int i:V2)dodaj(i);
		for(int i:V)usun(i);
		//return 0;
		/*if(t==1){
			cout<<quer(1)<<" "<<quer(2)<<" "<<quer(3)<<" "<<quer(4)<<"\n";
		}*/
		while(wsk<q && Q[wsk].st.st==t){
			ans[Q[wsk].st.nd]=quer(Q[wsk].nd.nd)-quer(Q[wsk].nd.st);
			wsk++;
		}
	}
	for(int i=0; i<q; i++)cout<<ans[i]<<"\n";
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80