제출 #1037909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1037909		AmirAli_H1	Fish 3 (JOI24_fish3)	C++17	100 / 100	457 ms	105840 KiB

Main

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, q;
const int maxn = 3e5 + 4;
const int maxlg = 20;
const ll oo = 1e18 + 4;
ll A[maxn], sm[maxn], val[maxn], D;
vector<pll> Q[maxn]; ll ans[maxn];
ll rmq[maxn][maxlg]; vector<pll> st;
pll t[4 * maxn];

void add_val(int v, int tl, int tr, int l, int r, ll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	if (l == tl && r == tr) {
		t[v].F += x; t[v].S += (tr - tl) * x;
		return ;
	}
	int mid = (tl + tr) / 2;
	add_val(2 * v + 1, tl, mid, l, r, x); add_val(2 * v + 2, mid, tr, l, r, x);
	t[v].S = t[2 * v + 1].S + t[2 * v + 2].S + (tr - tl) * t[v].F;
}

ll get_sum(int v, int tl, int tr, int l, int r) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return 0;
	if (l == tl && r == tr) return t[v].S;
	int mid = (tl + tr) / 2;
	return (r - l) * t[v].F + get_sum(2 * v + 1, tl, mid, l, r) + get_sum(2 * v + 2, mid, tr, l, r);
}

ll get_min(int l, int r) {
	int j = __lg(r - l);
	return min(rmq[l][j], rmq[r - (1 << j)][j]);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> D;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
		if (i - 1 >= 0) sm[i] = ((A[i - 1] % D) > (A[i] % D));
	}
	for (int i = 0; i < n; i++) {
		if (i - 1 >= 0) sm[i] += sm[i - 1];
		A[i] /= D; val[i] = (A[i] - sm[i]);
	}
	
	for (int i = n - 1; i >= 0; i--) {
		rmq[i][0] = val[i];
		for (int j = 1; j < maxlg; j++) {
			if (i + (1 << j) - 1 >= n) break;
			rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
		}
	}
	
	cin >> q;
	for (int i = 0; i < q; i++) {
		int l, r;
		cin >> l >> r; l--; r--;
		if (get_min(l, r + 1) + sm[l] < 0) ans[i] = -1;
		else Q[r].pb(Mp(l, i));
	}
	
	st.pb(Mp(-oo, -1));
	for (int i = 0; i < n; i++) {
		add_val(0, 0, n, i, i + 1, val[i]);
		while (val[i] <= st.back().F) {
			int lx = st[len(st) - 2].S + 1, rx = st[len(st) - 1].S + 1;
			add_val(0, 0, n, lx, rx, st.back().F); st.pop_back();
		}
		int lx = st[len(st) - 1].S + 1, rx = i + 1;
		add_val(0, 0, n, lx, rx, -val[i]); st.pb(Mp(val[i], i));
		
		for (auto f : Q[i]) {
			int l = f.F, j = f.S;
			ans[j] = get_sum(0, 0, n, l, i + 1);
		}
	}
	
	for (int i = 0; i < q; i++) cout << ans[i] << endl;
	
	return 0;
}

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