Submission #988469

#	Time	Username	Problem	Language	Result	Execution time	Memory
988469		amirhoseinfar1385	Fish 3 (JOI24_fish3)	C++17	100 / 100	251 ms	40544 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long maxn=300000+10;
long long n,q,d,all[maxn],res[maxn],suma[maxn],kaf=(1<<19);
vector<pair<long long,long long>>qu[maxn];
vector<long long>na;

struct fenwick{
	long long fen[maxn];
	void ins(long long i,long long w){
		i++;
		while(i<maxn){
			fen[i]+=w;
			i+=((-i)&i);
		}
	}
	long long pors(long long i){
		long long ret=0;
		i++;
		while(i>0){
			ret+=fen[i];
			i-=((-i)&i);
		}
		return ret;
	}
}fensuma,fenssum,fensumkam;

void vorod(){
	cin>>n>>d;
//	if(n>3000){
//		exit(0);
//	}
	for(long long i=1;i<=n;i++){
		cin>>all[i];
	}
	cin>>q;
	for(long long i=0;i<q;i++){
		long long l,r;
		cin>>l>>r;
		qu[r].push_back(make_pair(l,i));
	}
}

void ins(long long ind,long long w){
	fensuma.ins(na.back()+1,w);
	fensuma.ins(ind+1,-w);
	fenssum.ins(na.back()+1,w*ind);
	fenssum.ins(ind+1,-w*ind);
	fensumkam.ins(0,w*(ind-na.back()));
	fensumkam.ins(na.back()+1,-w*(ind-na.back()));
//	for(long long i=ind;i>na.back();i--){
//		suma[i]+=w;
//	}
}

long long check(long long ind){
	/*long long ted=suma[ind+1];
	long long z=all[ind]-suma[ind+1]*d;
	if(z>=all[ind-1]){
		return -1;
	}
	ted=(all[ind-1]-z)/d;
	if((all[ind-1]-z)%d!=0){
		ted++;
	}
	return ted;*/
	long long ted=0;
	long long z=all[ind]-fensuma.pors(ind+1)*d;
	if(z>=all[ind-1]){
		return -1;
	}
	ted=(all[ind-1]-z)/d;
	if((all[ind-1]-z)%d!=0){
		ted++;
	}
	return ted;
}


long long pors(long long ind){
	long long ret=0;
//	for(long long i=ind+1;i<=n;i++){
//		ret+=fensuma.pors(i);
//	}
	ret=fensumkam.pors(ind)+fenssum.pors(ind)-fensuma.pors(ind)*ind;
	if(fensuma.pors(ind+1)*d>all[ind]){
		return -1;
	}
	return ret;
}

void solve(){
	na.push_back(1);
	for(long long i=2;i<=n;i++){
		if(all[i]<all[i-1]){
			long long ted=(all[i-1]-all[i])/d;
			if((all[i-1]-all[i])%d!=0){
				ted++;
			}
			if(ted>0){
				ins(i,ted);
			}
			while((long long)na.back()>1){
				long long z=check(na.back());
				if(z==-1){
					break;
				}
				long long last=na.back();
				na.pop_back();
				ins(last,z);
			}
		}else{
			na.push_back(i);
		}
		for(auto x:qu[i]){
			res[x.second]=pors(x.first);
		}
	}
}

void khor(){
	for(long long i=0;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: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36