Submission #1265720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265720		witek_cpp	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	575 ms	133716 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define wczytaj(a, c, n) a.resize(n); f(i, c, n) cin >> a[i];
#define sz(a) int(a.size())
#define wypisz(a, c) f(i, c, sz(a)) cout << a[i] << " "; cout << "\n";

const int MAXLOG = 18;
const ll INF = 1'000'000'000'000'000;

vector<ll> a; //jaka odleglosc
vector<ll> b; //jaki koszt zakupu paliwa

vector<pair<ll, ll>> f_drzewo; //drzewo funkcji liniowych
vector<ll> odl_drzewo; //maksymalne drzewo po odl
vector<pair<ll, ll>> b_drzewo; //minimalne po koszcie paliwala

vector<ll> pref; //sumy prefiksowe do obliczania odleglosci
vector<ll> dpl; //tutaj tylko odl bo jp nie robimy
vector<pair<ll, int>> dpr; //jaka odleglosc do kolejnego tanszego na lewo i jaki to bedzie wierzcholek do jp
vector<vector<pair<ll, int>>> jp; //dokad doskaczymy i z jakim kosztem i z jaka odl

ll maks(int l, int r) {
	ll wnk = max(odl_drzewo[l], odl_drzewo[r]);
	while (r > (l + 1)) {
		if (l%2 == 0) {
			wnk = max(wnk, odl_drzewo[l + 1]);
		} 
		if (r%2 == 1) {
			wnk = max(wnk, odl_drzewo[r - 1]);
		}
		l /= 2;
		r /= 2;
	}
	return wnk;
}

void zmien(int ind, pair<ll, ll> zmiana) {
	f_drzewo[ind] = zmiana;
	ind /= 2;
	while (ind) {
		f_drzewo[ind] = {f_drzewo[ind * 2].st + f_drzewo[(ind * 2) + 1].st, f_drzewo[ind * 2].nd + f_drzewo[(ind * 2) + 1].nd};
		ind /= 2;
	}
}

int minn(int l, int r) {
	pair<ll, ll> wnk = min(b_drzewo[l], b_drzewo[r]);
	while (r > (l + 1)) {
		if (l%2 == 0) {
			wnk = min(wnk, b_drzewo[l + 1]);
		} 
		if (r%2 == 1) {
			wnk = min(wnk, b_drzewo[r - 1]);
		}
		l /= 2;
		r /= 2;
	}
	return wnk.nd;
}

pair<ll, ll> zlozenie(int l, int r) {
	pair<ll, ll> wnk = {0, 0};
	if (r < l) return wnk;
	if (r == l) return f_drzewo[r];
	wnk = {f_drzewo[r].st + f_drzewo[l].st, f_drzewo[r].nd + f_drzewo[l].nd};
	while (r > (l + 1)) {
		if (l%2 == 0) {
			wnk.st += f_drzewo[l + 1].st;
			wnk.nd += f_drzewo[l + 1].nd;
		} 
		if (r%2 == 1) {
			wnk.st += f_drzewo[r - 1].st;
			wnk.nd += f_drzewo[r - 1].nd;
		}
		r /= 2;
		l /= 2;
	}
	return wnk;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n>> q;
	a.resize(n);
	b.resize(n);
	f(i, 0, n) cin >> a[i];
	f(i, 0, n) cin >> b[i];
	
	pref.resize(n + 1);
	pref[0] = 0;
	f(i, 1, n + 1) pref[i] = pref[i - 1] + a[i - 1];
	dpl.resize(n);
	stack<int> stos; //stos monotoniczny gdzie trzymam tylko ind
	f(i, 0, n) {
		while (sz(stos) && b[stos.top()] > b[i]) stos.pop();
		if (sz(stos)) {
			dpl[i] = pref[i] - pref[stos.top()];
		} else {
			dpl[i] = INF;
		}
		stos.push(i);
	}
	
	dpr.resize(n); //resizuje bo bede robic teraz stos monotoniczny i zapisywac wyniki
	stos = {};
	for (int i = n - 1; i >= 0; i--) {
		while (sz(stos) && b[stos.top()] >= b[i]) stos.pop();
		if (sz(stos)) {
			dpr[i] = {pref[stos.top()] - pref[i], stos.top()};
		} else {
			dpr[i] = {INF, -1};
		}
		stos.push(i);
	}	
	
	int stala = 1;
	while (stala < n) stala *= 2;
	
	odl_drzewo.resize((stala + 1) * 2);
	f(i, 0, n) odl_drzewo[i + stala] = a[i];
	f(i, n, stala) odl_drzewo[i + stala] = -INF;
	for (int j = stala - 1; j > 0; j--) {
		odl_drzewo[j] = max(odl_drzewo[j * 2], odl_drzewo[(2 * j) + 1]);
	}
	
	b_drzewo.resize((stala + 1) * 2);
	f(i, 0, n) b_drzewo[i + stala] = {b[i], i};
	f(i, n, stala) b_drzewo[i + stala] = {INF, INF};
	for (int j = stala - 1; j > 0; j--) {
		b_drzewo[j] = min(b_drzewo[j * 2], b_drzewo[(j * 2) + 1]);
	}
	
	jp.resize(MAXLOG, vector<pair<ll, int>>(n));
	
	f(i, 0, n) {
		if (dpr[i].st == INF) {
			jp[0][i] = {0, i};
		} else {
			jp[0][i] = {b[i] * dpr[i].st, dpr[i].nd};
		}
	}
	f(j, 1, MAXLOG) {
		f(i, 0, n) {
			jp[j][i] = {jp[j - 1][i].st + jp[j - 1][jp[j - 1][i].nd].st, jp[j - 1][jp[j - 1][i].nd].nd};
		}
	}
	
	//na poc kazda funkcja ma y = x + 0
	f_drzewo.resize((stala + 1) * 2);
	f(i, 0, n) {
		f_drzewo[i + stala] = {b[i], 0};
	}
	f(i, n, stala) {
		f_drzewo[i + stala] = {0, 0};
	}
	for (int j = stala - 1; j > 0; j--) {
		f_drzewo[j] = {f_drzewo[j * 2].st + f_drzewo[(j * 2) + 1].st, f_drzewo[j * 2].nd + f_drzewo[(j * 2) + 1].nd};
	}
	
	vector<pair<ll, pair<int, pair<int, pair<ll, ll>>>>> zamiatanie; //{jaki czas, {jaki rodzaj, {jaki ind, na co}}}
	f(i, 0, n) {
		zamiatanie.pb({min(dpl[i], dpr[i].st), {0, {i, {0, min(dpl[i], dpr[i].st) * b[i]}}}});
		zamiatanie.pb({max(dpl[i], dpr[i].st), {1, {i, {-b[i], (dpl[i] + dpr[i].st) * b[i]}}}});
		zamiatanie.pb({dpl[i] + dpr[i].st, {2, {i, {0, 0}}}});
	}
	
	vector<pair<pair<int, int>, ll>> pytania(q);
	vector<ll> odp(q);
	
	int ile_zrobione = 0;
	
	f(i, 0, q) {
		int l, r;
		ll u;
		cin >> l >> r >> u;
		l--;
		r--;
		pytania[i] = {{l, r}, u};
		if (maks(l + stala, r + stala - 1) > u) {
			ile_zrobione++;
			odp[i] = -1;
		} else {
			zamiatanie.pb({u, {3, {i, {-1, -1}}}});
		}
	}
	
	sort(all(zamiatanie));
	reverse(all(zamiatanie));
	
	while (ile_zrobione < q) {
		if (zamiatanie.empty()) {
			cout << "blad";
			return 0;
		}
		pair<ll, pair<int, pair<int, pair<ll, ll>>>> p1 = zamiatanie.back();
		zamiatanie.pop_back();
		int rodzaj = p1.nd.st;
		int ind = p1.nd.nd.st;
		if (rodzaj != 3) {
			zmien(ind + stala, p1.nd.nd.nd);
			continue;
		}
		ll aktl_u = pytania[ind].nd;
		int l, r, mid; //by znalezc gdzie sie konczy nasz przedzial
		int koniec = pytania[ind].st.nd;
		r = pytania[ind].st.nd - 1;
		l = pytania[ind].st.st;
		while (r > l) {
			mid = (l + r)/2;
			if ((pref[koniec] - pref[mid]) <= aktl_u) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		int suf_min = minn(r + stala, koniec - 1 + stala);
		//cout << "o suf min pytam sie na przedziale " << r << " ... " << koniec - 1 << "\n";
		//cout << "ind min suf to " << suf_min << "\n";
		int poc = pytania[ind].st.st;
		int skacze = poc;
		ll ile_doda_skaczac = 0;
		for (int j = MAXLOG - 1; j >= 0; j--) {
			int p2 = jp[j][skacze].nd;
			if ((pref[p2] - pref[poc]) <= aktl_u && p2 < koniec) {
				ile_doda_skaczac += jp[j][skacze].st;
				skacze = p2;
			}
		}
		//cout << "skad start to " << skacze << "\n";
		pair<ll, ll> nowa_funkcja = zlozenie(skacze + stala + 1, suf_min - 1 + stala);
		//cout << "ile doda poc " << ile_doda_skaczac << "\n";
		ll ile_doda_punkt = 0;
		if (skacze < suf_min) {
			ile_doda_punkt = min(pref[koniec] - pref[skacze], min(aktl_u, dpr[skacze].st)) * b[skacze];
		}
		ll ile_doda_srodek = aktl_u * nowa_funkcja.st + nowa_funkcja.nd;
		//cout << "suf min to " << suf_min << "\n";
		//cout << "skacze to " << skacze << "\n";
		//cout << "ile doda srodek " << ile_doda_srodek << " ile doda start " << ile_doda_skaczac << "\n";
		ll ile_doda_kon = ((pref[koniec] - pref[suf_min]) * b[suf_min]);
		if (dpl[suf_min] <= (pref[suf_min] - pref[poc])) {
			ile_doda_kon -= (b[suf_min] * max((ll)0, (aktl_u - dpl[suf_min])));
		}
		//cout << "ile doda start " << ile_doda_skaczac << "  ile doda srodek " << ile_doda_srodek << "  ile doda kon " << ile_doda_kon << "  ile doda punkt " << ile_doda_punkt << "\n";
		odp[ind] = ile_doda_skaczac + ile_doda_srodek + ile_doda_kon + ile_doda_punkt;
		ile_zrobione++;
	}
	
	for (ll ele: odp) {
		cout << ele << "\n";
	}
	
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44