제출 #1010554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010554		dozer	Fish 3 (JOI24_fish3)	C++14	9 / 100	1336 ms	47188 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005
#define LL node * 2
#define RR node * 2 + 1
#define mid (l + r) / 2
#define LOGN 20
#define S 2
#define int long long

const int modulo = 1e9 + 7;
const long long INF = 2e18 + 7;

vector<int> gaps[N], pre[N];
int last[N], ans[N];

int32_t main()
{
	fastio();


	int n, d;
	cin>>n>>d;
	vector<int> arr(n + 5, 0);
	for (int i = 1; i <= n; i++)
		cin>>arr[i];

	for (int i = 1; i <= n; i++){
		if (i % S == 0){
			int curr = arr[i];
			for (int j = i - 1; j > i - S; j--){
				int diff = max((int)0, arr[j] - curr);
				int cnt = (diff + d - 1) / d;
				ans[i] += cnt;
				int tmp = arr[j] - cnt * d;
				int gap = (curr - tmp) / d;
				if (gaps[i].empty()) gaps[i].pb(gap);
				else gaps[i].pb(gaps[i].back() + gap);
				if (pre[i].empty()) pre[i].pb(gaps[i].back());
				else pre[i].pb(pre[i].back() + gaps[i].back());
				curr = tmp;
			}
			last[i] = curr;
			reverse(gaps[i].begin(), gaps[i].end());
		}
	}

	auto solve = [&](int l, int r){
		int curr = arr[r];
		int res = 0;
		while(r >= l && r % S != 0){
			int diff = max((int)0, arr[r] - curr);
			int cnt = (diff + d - 1) / d;
			int tmp = arr[r] - d * cnt;
			res += cnt;
			curr = tmp;
			r--;
		}

		/*
		//cout<<r<<sp<<res<<endl;
		while(r - S >= l){
			res += ans[r];
			if (curr >= arr[r]){
				curr = last[r];
				r -= S;
			}
			else{
				int diff = arr[r] - curr;
				int cnt = (diff + d - 1) / d;
				res += cnt;
				int pos = lower_bound(gaps[r].begin(), gaps[r].end(), cnt) - gaps[r].begin();
				curr = last[r];

				if (pos == gaps[r].size()){
					pos--;
					curr -= (cnt - gaps[r][pos]) * d;
				}
				int sz = pos + 1;
				res += cnt * sz;
				res -= pre[r][pos];
				r -= S;
			}
		}
	*/
		//cout<<r<<sp<<res<<sp<<curr<<endl;
		while(r >= l){
			int diff = max((int)0, arr[r] - curr);
			int cnt = (diff + d - 1) / d;
			res += cnt;
			curr = arr[r] - cnt * d;
			r--;
		}

		if (curr < 0) return (int)-1;
		return res;
	};


	int q;
	cin>>q;
	while(q--){
		int l, r;
		cin>>l>>r;
		cout<<solve(l, r)<<endl;
	}

	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

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