Submission #1161863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161863		irmuun	Fish 3 (JOI24_fish3)	C++20	28 / 100	297 ms	42388 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtree{
	ll n;
	vector<ll>d;
	segtree(ll n){
		d.resize(4*n);
	}
	ll query(ll v,ll l,ll r,ll L,ll R){
		if(R<L||r<L||R<l) return 0;
		if(L<=l&&r<=R) return d[v];
		ll mid=(l+r)>>1;
		return query(v<<1,l,mid,L,R)+query(v<<1|1,mid+1,r,L,R);
	}
	void update(ll v,ll l,ll r,ll pos,ll val){
		if(r<pos||pos<l) return;
		if(l==r){
			d[v]=val;
			return;
		}
		ll mid=(l+r)>>1;
		update(v<<1,l,mid,pos,val);
		update(v<<1|1,mid+1,r,pos,val);
		d[v]=d[v<<1]+d[v<<1|1];
	}
};

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	ll n,d;
	cin>>n>>d;
	ll c[n+5],pre[n+5];
	pre[0]=0;
	for(ll i=1;i<=n;i++){
		cin>>c[i];
		pre[i]=pre[i-1]+c[i];
	}
	ll q;
	cin>>q;
	vector<array<ll,3>>que;
	vector<ll>ans(q);
	for(ll i=0;i<q;i++){
		ll l,r;
		cin>>l>>r;
		que.pb({r,l,i});
	}
	segtree sg(n);
	sort(all(que));
	ll cur=0,sum=0;
	vector<array<ll,3>>v;
	for(ll R=1;R<=n;R++){
		sum+=c[R];
		ll cnt=1;
		while(!v.empty()){
			if(v.back()[2]>=c[R]){
				cnt+=v.back()[1]-v.back()[0]+1;
				v.pop_back();
			}
			else break;
		}
		v.pb({R-cnt+1,R,c[R]});
		sg.update(1,0,n-1,v.size()-1,(pre[R]-pre[R-cnt])-cnt*c[R]);
		while(cur<q&&que[cur][0]==R){
			auto [r,l,j]=que[cur++];
			array<ll,3>p;
			p={l,n+5,0ll};
			auto it=upper_bound(all(v),p)-v.begin();
			ans[j]+=sg.query(1,0,n-1,it,v.size()-1);
			ll L;
			if(it==v.size()){
				L=R+1;
			}
			else{
				L=v[it][0];
			}
			it--;
			ans[j]+=(pre[L-1]-pre[l-1])-(L-l)*v[it][2];
		}
	}
	for(ll i=0;i<q;i++){
		cout<<ans[i]<<"\n";
	}
}

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