Submission #996869

#	Time	Username	Problem	Language	Result	Execution time	Memory
996869		errorgorn	Fish 3 (JOI24_fish3)	C++17	100 / 100	450 ms	118964 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,k,q;
int arr[300005];
int brr[300005];

int pref1[300005];
int pref2[300005];

ii nxt[300005][20];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>k;
	rep(x,1,n+1) cin>>arr[x];
	rep(x,1,n+1) brr[x]=arr[x-1]-arr[x];
	
	int L=1e18/k;
	rep(x,1,n+1) brr[x]+=(-brr[x]+k*L)%k;
	
	rep(x,1,n+1) pref1[x]=pref1[x-1]+brr[x];
	rep(x,1,n+1) pref2[x]=pref2[x-1]+brr[x]*x;
	
	int P=0;
	vector<ii> v={{4e18,0}};
	rep(x,1,n+1){
		P+=brr[x];
		while (!v.empty() && v.back().fi<P) v.pob();
		
		int y=v.back().se;
		nxt[x][0]={y,(pref2[x]-pref2[y+1])-(pref1[x]-pref1[y+1])*(y+1)};
		
		v.pub({P,x});
	}
	
	rep(y,1,20) rep(x,1,n+1){
		int u=nxt[x][y-1].fi;
		
		nxt[x][y]={
			nxt[u][y-1].fi,
			nxt[x][y-1].se+nxt[u][y-1].se
		};
	}
	
	cin>>q;
	while (q--){
		int l,r; cin>>l>>r;
		
		int ans=0;
		
		rep(x,20,0) if (nxt[r][x].fi>=l){
			ans+=nxt[r][x].se;
			r=nxt[r][x].fi;
		}
		
		ans+=(pref2[r]-pref2[l])-(pref1[r]-pref1[l])*(l);
		
		int v=arr[l]-(pref1[r]-pref1[l]);
		
		if (v<0) cout<<"-1"<<endl;
		else cout<<ans/k<<endl;
	}
}

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