Submission #979444

#	Time	Username	Problem	Language	Result	Execution time	Memory
979444		penguin133	Fish 3 (JOI24_fish3)	C++17	100 / 100	224 ms	47484 KiB

Main

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

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, d, q, A[300005], val[300005], P[300005], grr[300005];
vector <pii> Q;
int ans[300005];
pi brr[300005];

void dnc(int l, int r, vector <pii> &qu){
	if(l >= r)return;
	int mid = (l + r) >> 1;
	vector <pii> lft, rgt, gd;
	for(auto i : qu){
		if(i.fi > mid)rgt.push_back(i);
		else if(i.se.fi <= mid)lft.push_back(i);
		else gd.push_back(i);
	}
	dnc(l, mid, lft);
	dnc(mid + 1, r, rgt);
	brr[mid + 1] = {0, 0};
	int cur_sum = 0, cur_one = 0;
	stack <pi> s;
	s.push({1e18, mid});
	for(int i = mid + 2; i <= r; i++){
		if(A[i] >= A[i - 1])s.push({(A[i] - A[i - 1]) / d, i - 1});
		else{
			int tmp = (A[i - 1] - A[i] + d - 1) / d;
			cur_sum += tmp * (i - 1 - s.top().se);
			if(s.top().se == mid)cur_one += tmp;
			while(!s.empty() && tmp){
				pi x = s.top();
				s.pop();
				if(x.fi > tmp){
					x.fi -= tmp;
					s.push(x);
					break;
				}
				tmp -= x.fi;
				assert(!s.empty());
				cur_sum += (x.se - s.top().se) * tmp;
				if(s.top().se == mid)cur_one += tmp;
			}
		}
		brr[i] = {cur_sum, cur_one};
	}
	int prv = A[mid], cur = 0;
	brr[mid] = {0, A[mid]};
	val[mid] = 0;
	for(int i = mid - 1; i >= l; i--){
		if(A[i] <= prv){
			brr[i] = {cur, A[i]};
			val[i] = (prv - A[i]) / d;
			prv = A[i];
			continue;
		}
		int ops = (A[i] - prv + d - 1) / d;
		val[i] = 0;
		prv = A[i] - ops * d;
		cur += ops;
		brr[i] = {cur, prv};
	}
	P[l - 1] = grr[l - 1] = 0;
	for(int i = l; i <= mid; i++)P[i] = P[i - 1] + val[i], grr[i] = grr[i - 1] + val[i] * (i + 1);
	for(auto i : gd){
		int lend = i.fi, rend = i.se.fi;
		if(brr[lend].se < 0 || A[mid + 1] - brr[rend].se * d < 0){
			ans[i.se.se] = -1;
			continue;
		}
		int lo = lend, hi = mid, tmp = lo, ops = 0, ops_one = 0;
		int rem = A[mid + 1] - brr[rend].se * d;
		int req = (A[mid] - rem + d - 1) / d;
		req = max(req, 0ll);
		while(lo <= hi){
			int mm = (lo + hi) >> 1;
			if(P[mid] - P[mm - 1] >= req)tmp = mm, lo = mm + 1;
			else hi = mm - 1;
		}
		//cout << lend << ' ' << rend << ' ' << tmp << ' ' << req << ' ' << rem << '\n';
		//cout << P[mid] - P[tmp - 1] << '\n';
		if(P[mid] - P[tmp - 1] <= req){
			ops = req * (mid - lend + 1) - (grr[mid] - grr[tmp - 1]) + lend * (P[mid] - P[tmp - 1]);
			if(tmp == lend)ops_one += req - P[mid] + P[tmp - 1];
		}
		else{
			int x = P[mid] - P[tmp];
			ops += req * (mid - lend + 1) - (grr[mid] - grr[tmp]) + lend * x;
			rem = req - x;
			ops -= rem * (tmp + 1);
			ops += lend * rem;
		}
		if(brr[lend].se - ops_one * d < 0)ans[i.se.se] = -1;
		else ans[i.se.se] = brr[lend].fi + brr[rend].fi + ops;
	}
}

void solve(){
	cin >> n >> d;
	for(int i = 1; i <= n; i++)cin >> A[i];
	for(int i = 1; i < n; i++){
		if(A[i] < A[i + 1]){
			val[i] = (A[i + 1] - A[i]) / d;
		}
		P[i] = P[i - 1] + val[i];
		grr[i] = grr[i - 1] + val[i] * (i + 1);
	}
	cin >> q;
	/*
	while(q--){
		int l, r; cin >> l >> r;
		int cur = 0, f = 1, prv = A[r];
		for(int i = r - 1; i >= l; i--){
			int df = A[i] - prv;
			if(df < 0){
				prv = A[i];
				continue;
			}
			int tmp = (df + d - 1) / d;
			if(A[i] - tmp * d < 0){
				f = 0;
				break;
			}
			prv = A[i] - tmp * d;
			cur += (df + d - 1) / d;
		}
		if(!f){
			cout << -1 << '\n';
			continue;
		}
		cout << cur << '\n';
	}
	*/
	for(int i = 1; i <= q; i++){
		int l, r;
		cin >> l >> r;
		if(l == r)ans[i] = 0;
		else Q.push_back({l, {r, i}});
	}
	dnc(1, n, Q);
	for(int i = 1; i <= q; i++)cout << ans[i] << '\n';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

Main.cpp:153:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  153 | main(){
      | ^~~~

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