Submission #1010658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010658		dozer	Fish 3 (JOI24_fish3)	C++14	100 / 100	744 ms	272812 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 400005
#define LL node * 2
#define RR node * 2 + 1
#define mid (l + r) / 2
#define LOGN 20
#define int long long

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

	
int arr[N], d;

struct Node{
	int start, last, ans;
	vector<int> pre, gaps;
	int L, R;
	Node(){};
	Node(int l, int r){
		//cout<<l<<sp<<r<<" : ";
		L = l, R = r;
		gaps.pb(0);
		pre.pb(0);
		ans = 0;
		int curr = arr[r];
		start = arr[r];
		r--;
		while(r >= l){
			int cnt = (max((int)0, arr[r] - curr) + d - 1) / d;
			ans += cnt;
			int tmp = arr[r] - cnt * d;
			int g = (curr - tmp) / d;
			gaps.pb(gaps.back() + g);
			pre.pb(pre.back() + gaps.back());
			curr = tmp;
			r--;
		}
		last = curr;
		//cout<<start<<sp<<last<<sp<<ans<<endl;
	}

	pii merge(int curr, int res){
		res += ans;
		if (curr < 0) return {curr, -1};

		if (start <= curr) {
			if (last < 0) return {last, -1};
			return {last, res};
		}

		int diff = start - curr;
		int cnt = (diff + d - 1) / d;
		res += cnt;


		if (gaps.size() == 1) {
			curr = last - cnt * d;
			if (curr < 0) return {curr, -1};
			return {curr, res};
		}

		int pos = lower_bound(gaps.begin(), gaps.end(), cnt) - gaps.begin();

		curr = last;
		if (pos == gaps.size()){
			pos--;
			curr -= (cnt - gaps[pos]) * d;
		}

		int sz = pos;
		res += cnt * sz;
		res -= pre[pos];
		if (gaps[pos] > cnt) res += gaps[pos] - cnt;

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




struct SegTree{
	vector<Node> tree;
	int n;
	void build(int node, int l, int r){
		tree[node] = Node(l, r);
		if (l == r) return;
		build(LL, l, mid);
		build(RR, mid + 1, r);
	}
	SegTree(int sz){
		n = sz;
		tree.resize(4 * n + 5);
		build(1, 1, n);
	}

	pii query(int node, int l, int r, int sl, int sr, int curr, int res){
		if (l >= sl && r <= sr) return tree[node].merge(curr, res);
		if (sl > mid) return query(RR, mid + 1, r, sl, sr, curr, res);
		if (sr <= mid) return query(LL, l, mid, sl, sr, curr, res);
		pii tmp = query(RR, mid + 1, r, sl, sr, curr, res);
		return query(LL, l, mid, sl, sr, tmp.st, tmp.nd);
	}
};


int32_t main()
{
	fastio();

	int n;
	cin>>n>>d;
	for (int i = 1; i <= n; i++){
		cin>>arr[i];
	}

	SegTree tree(n);
	int q;
	cin>>q;
	while(q--){
		int l, r;
		cin>>l>>r;
		pii tmp = tree.query(1, 1, n, l, r, INF, 0); 
		cout<<tmp.nd<<endl;
	}
	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

Compilation message (stderr)

Main.cpp: In member function 'std::pair<long long int, long long int> Node::merge(long long int, long long int)':
Main.cpp:74:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   if (pos == gaps.size()){
      |       ~~~~^~~~~~~~~~~~~~

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