Submission #1135262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135262		emptypringlescan	Fish 3 (JOI24_fish3)	C++17	100 / 100	309 ms	58660 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n;
long long d;
long long arr[300005];
struct node{
	long long val,lazy;
	int s,e,m;
	node *l,*r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
		val=lazy=0;
	}
	void prop(){
		if(lazy){
			l->val+=(long long)lazy*(m-s+1);
			l->lazy+=lazy;
			r->val+=(long long)lazy*(e-m);
			r->lazy+=lazy;
			lazy=0;
		}
	}
	void update(int S, int E, long long V){
		if(S<=s&&e<=E){
			val+=(long long)V*(e-s+1);
			lazy+=V;
			return;
		}
		prop();
		if(E<=m) l->update(S,E,V);
		else if(S>m) r->update(S,E,V);
		else l->update(S,m,V),r->update(m+1,E,V);
		val=l->val+r->val;
	}
	long long query(int S, int E){
		if(S<=s&&e<=E) return val;
		prop();
		if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else return l->query(S,m)+r->query(m+1,E);
	}
} *root;
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> d;
	for(int i=1; i<=n; i++) cin >> arr[i];
	int q;
	cin >> q;
	pair<pair<int,int>,int> qu[q];
	for(int i=0; i<q; i++){
		cin >> qu[i].first.second >> qu[i].first.first;
		qu[i].second=i;
	}
	sort(qu,qu+q);
	root=new node(1,n);
	vector<pair<pair<int,int>,pair<long long,long long> > > seg;
	int cnt=0;
	long long ans[q];
	for(int i=1; i<=n; i++){
		pair<pair<int,int>,pair<long long,long long> > cur={{i,i},{arr[i],arr[i]}};
		while(!seg.empty()&&seg.back().second.second>cur.second.first){
			long long need=(seg.back().second.second-cur.second.first-1)/d+1;
			root->update(seg.back().first.first,seg.back().first.second,need);
			cur.first.first=seg.back().first.first;
			cur.second.first=seg.back().second.first-need*d;
			seg.pop_back();
		}
		seg.push_back(cur);
		while(cnt<q&&qu[cnt].first.first==i){
			int a=qu[cnt].first.second,b=qu[cnt].first.first;
			int c=qu[cnt].second;
			cnt++;
			if(arr[a]-root->query(a,a)*d<0){
				ans[c]=-1;
				continue;
			}
			ans[c]=root->query(a,b);
		}
	}
	for(int i=0; i<q; i++) cout << ans[i] << '\n';
}

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36