제출 #1036812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036812		Tob	Fish 3 (JOI24_fish3)	C++14	100 / 100	274 ms	42896 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 3e5 + 7;

ll n, q, d;
ll c[N], ps[N], kol[N], res[N];
vector <pii> qu[N];
ll fen[2][N];

void add(int o, int x, ll val) {for (x++; x < N; x += x & -x) fen[o][x] += val;}
ll get(int o, int x) {ll out = 0; for (x++; x; x -= x & -x) out += fen[o][x]; return out;}
void update(int l, int r, ll val) {add(0, l, val); add(0, r+1, -val); add(1, l, val*l); add(1, r+1, -val*(r+1));}
ll query(int x) {return get(0, x)*x-get(1, x);}
ll query(int l, int r) {return query(r+1)-query(l);}

int main () {
	FIO;
	cin >> n >> d;
	for (int i = 0; i < n; i++) cin >> c[i];
	for (int i = 1; i < n; i++) kol[i] = kol[i-1] + (c[i-1]%d > c[i]%d);
	for (int i = 0; i < n; i++) {
		ps[i+1] = ps[i] + c[i]/d;
		c[i] = c[i]/d-kol[i];
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int l, r; cin >> l >> r; l--; r--;
		qu[r].pb({l, i});
	}
	
	stack <pii> st;
	st.push({-1, (ll)-1e18});
	for (int i = 0; i < n; i++) {
		update(i, i, c[i]+kol[i]);
		while (!st.empty() && st.top().S >= c[i]) {
			ll x = st.top().F, y = st.top().S; st.pop();
			update(st.top().F+1, x, c[i]-y);
		}
		st.push({i, c[i]});
		for (auto x : qu[i]) res[x.S] = ((query(x.F, x.F) < 0) ? -1 : ps[i+1]-ps[x.F]-query(x.F, i));
	}
	for (int i = 0; i < q; i++) cout << res[i] << "\n";

	return 0;
}

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