제출 #1248839

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248839		Bui_Quoc_Cuong	Fish 3 (JOI24_fish3)	C++20	100 / 100	475 ms	46772 KiB

Main

# include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxN = 5e5 + 5;

int n, D, q;
int a[maxN];
vector <array <int, 2>> off[maxN];
long long ans[maxN];

struct SegmentTree {
	long long st[4 * maxN], lazy[4 * maxN];

	void apply(int id, long long val, int l, int r) {
		st[id]+= 1LL * (r - l + 1) * val;
		lazy[id]+= val;
	}	

	void pushDown(int id, int l, int r) {
		if (lazy[id]) {
			apply(id << 1, lazy[id], l, (l + r) / 2);
			apply(id << 1 | 1, lazy[id], (l + r) / 2 + 1, r);
			lazy[id] = 0;
		}
	}

	void update(int id, int l, int r, int u, int v, int val) {
		if (l > v || r < u) return;
		if (l >= u && r <= v) {
			apply(id, val, l, r);
			return;
		}
		int mid = (l + r) >> 1;
		pushDown(id, l, r);
		update(id << 1, l, mid, u, v, val);
		update(id << 1 | 1, mid + 1, r, u, v, val);
		st[id] = st[id << 1] + st[id << 1 | 1];
	}

	long long get(int id, int l, int r, int u, int v) {
		if (l > v || r < u) return 0;
		if (l >= u && r <= v) return st[id];
		pushDown(id, l, r);
		int mid = (l + r) >> 1;
		return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
	} 
} ST;

signed main () {
	ios_base :: sync_with_stdio(0); cin.tie(0);
	
	// freopen("kieuoanh.inp", "r", stdin);
	// freopen("kieuoanh.out", "w", stdout);

	cin >> n >> D;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int l, r; cin >> l >> r;
		off[r].push_back({l, i});
	}

	stack <int> st;

	for (int i = 1; i <= n; i++) {
		int cur = i;
		while (!st.empty()) {
			int x = a[cur - 1] - ST.get(1, 1, n, cur - 1, cur - 1) * D;
			int y = a[cur] - ST.get(1, 1, n, cur, cur) * D;
			if (x <= y) break;
			int need = (x - y - 1) / D + 1;
			ST.update(1, 1, n, st.top(), cur - 1, need);
			cur = st.top();
			st.pop();			
		}
		st.push(cur);
		for (auto x : off[i]) {
			int l = x[0], id = x[1];
			if (a[l] - ST.get(1, 1, n, l, l) * D < 0) {
				ans[id] = - 1;
			} else {
				ans[id] = ST.get(1, 1, n, l, i);
			}
		}
	}

	for (int i = 1; i <= q; i++) {
		cout << ans[i] << "\n";
	}

	return 0;
}

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