Submission #967737

#	Time	Username	Problem	Language	Result	Execution time	Memory
967737		amirhoseinfar1385	Fire (JOI20_ho_t5)	C++17	100 / 100	628 ms	137420 KiB

ho_t5

#include<bits/stdc++.h>
using namespace std;
const long long maxn=400000+10;
struct fenwick{
	long long fn[maxn];
	void clear(){
		for(long long i=0;i<maxn;i++){
			fn[i]=0;
		}
	}
	void upd(long long l,long long r,long long w){
		//cout<<"upd: "<<l<<" "<<r<<" "<<w<<endl;
		l++;
		r++;
		if(l>r){
			return ;
		}
		r++;
		while(l<maxn){
			fn[l]+=w;
			l+=((-l)&l);
		}
		while(r<maxn){
			fn[r]-=w;
			r+=((-r)&r);
		}
	}
	long long pors(long long i){
		long long ret=0;
		i++;
		while(i>0){
			ret+=fn[i];
			i-=((-i)&i);
		}
		return ret;
	}
}sumw,sumwe;
struct que{
	long long ind,l,r;
}allq[maxn];
struct ezaf{
	long long sot,pa,tp,w;
	long long qq,radif,soton,z;
	ezaf(){
		qq=-1;
	}
};
long long n,q;
long long all[maxn],dpl[maxn],dpr[maxn],res[maxn];
vector<ezaf>amood,mov;

void vorod(){
	cin>>n>>q;
	for(long long i=1;i<=n;i++){
		cin>>all[i];
	}
	for(long long i=1;i<=q;i++){
		cin>>allq[i].ind>>allq[i].l>>allq[i].r;
	}
}

void caldp(){
	vector<long long>v;
	for(long long i=1;i<=n;i++){
		while((long long)v.size()>0&&all[v.back()]<=(long long)all[i]){
			v.pop_back();
		}
		if((long long)v.size()==0){
			dpl[i]=-1;
		}else{
			dpl[i]=v.back();
		}
		v.push_back(i);
	}
	v.clear();
	for(long long i=n;i>=1;i--){
		while((long long)v.size()>0&&all[v.back()]<(long long)all[i]){
			v.pop_back();
		}
		if((long long)v.size()==0){
			dpr[i]=-1;
		}else{
			dpr[i]=v.back();
		}
		v.push_back(i);
	}
}

void pre(){
	caldp();
	for(long long i=1;i<=q;i++){
		ezaf e;
		e.qq=i;
		e.radif=allq[i].ind;
		e.soton=allq[i].l-1;
		e.z=-1;
		amood.push_back(e);
		mov.push_back(e);
		e.soton=allq[i].r;
		e.z=1;
		amood.push_back(e);
		mov.push_back(e);
	}
	for(long long i=1;i<=n;i++){
		long long lenamood,lenmov;
		if(dpl[i]==-1){
			lenamood=n+5;
		}else{
			lenamood=i-dpl[i];
		}
		if(dpr[i]==-1){
			lenmov=n+5;
		}else{
			lenmov=dpr[i]-i;
		}
		////cout<<"chy: "<<i<<" "<<lenamood<<" "<<lenmov<<endl;
		ezaf e;
		e.sot=i;
		e.pa=0;
		e.tp=lenamood-2;
		e.w=all[i];
		amood.push_back(e);
		e.pa=lenamood-1;
		e.tp=lenamood-1+lenmov-1;
		mov.push_back(e);
		e.sot=i+1;
		e.pa=0;
		e.tp=lenmov-2;
		e.w=-all[i];
		mov.push_back(e);
		e.sot=i+1+lenmov-2+1;
		e.pa=lenmov-2+1;
		e.tp=e.pa+lenamood-1;
		amood.push_back(e);
	}
}

bool cmpamood(ezaf a,ezaf b){
	long long la,lb;
	if(a.qq==-1){
		la=a.sot;
	}else{
		la=a.soton;
	}
	if(b.qq==-1){
		lb=b.sot;
	}else{
		lb=b.soton;
	}
	if(la==lb){
		return a.qq<b.qq;
	}
	return la<lb;
}

bool cmpmov(ezaf a,ezaf b){
	long long la,lb;
	if(a.qq==-1){
		la=a.sot-a.pa;
	}else{
		la=a.soton-a.radif;
	}
	if(b.qq==-1){
		lb=b.sot-b.pa;
	}else{
		lb=b.soton-b.radif;
	}
	if(la==lb){
		return a.qq<b.qq;
	}
	return la<lb;
}

void solve(){
	sort(amood.begin(),amood.end(),cmpamood);
	sort(mov.begin(),mov.end(),cmpmov);
	for(auto x:amood){
		if(x.qq==-1){
		//	//cout<<"wtf: "<<x.w<<endl;
			sumw.upd(x.pa,x.tp,x.w);
			sumwe.upd(x.pa,x.tp,-x.w*(x.sot-1));
		}else{
			//cout<<"pors: "<<x.qq<<" "<<x.radif<<" "<<x.soton<<endl;
			long long fake=sumw.pors(x.radif)*x.soton+sumwe.pors(x.radif);
			res[x.qq]+=fake*x.z;
		}
	}
	sumw.clear();
	sumwe.clear();
	for(auto x:mov){
		if(x.qq==-1){
			////cout<<"wtf: "<<x.sot<<" "<<x.pa<<" "<<x.tp<<endl;
			//cout<<x.sot<<" hey:"<<endl;
			sumw.upd(x.pa,x.tp,x.w);
			sumwe.upd(x.pa,x.tp,-x.w*(x.sot-x.pa-1));
		}else{
			//cout<<"pors: "<<x.qq<<" "<<x.radif<<" "<<x.soton<<endl;
			long long fake=sumw.pors(x.radif)*(x.soton-x.radif)+sumwe.pors(x.radif);
			res[x.qq]+=fake*x.z;
		}
	}
}

void khor(){
	for(long long i=1;i<=q;i++){
		cout<<res[i]<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
	khor();
}

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