Submission #697729

#	Time	Username	Problem	Language	Result	Execution time	Memory
697729		flappybird	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	614 ms	71448 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
typedef pair<ll, int> pli;
pll operator+(pll p1, pll p2) {
	return pll(p1.first + p2.first, p1.second + p2.second);
}
pll operator-(pll p1) {
	return pll(-p1.first, -p1.second);
}
struct fenwick {
	vector<pll> tree;
	int N;
	fenwick(int N = 0) :N(N) { tree.resize(N + 1); }
	void upd(int i, pll x) { while (i <= N) { tree[i] = tree[i] + x, i += i & -i; } }
	pll get(int i) { pll ans = pll(0, 0); while (i) { ans = ans + tree[i], i -= i & -i; } return ans; }
	void update(int l, int r, pll x) {
		if (r <= 0) return;
		if (l > r) return;
		upd(l, x);
		if (r <= N) upd(r + 1, -x);
	}
};
struct segtree {
	int N;
	vector<pii> tree, arr;
	int mod = 0;
	pii zero;
	segtree(int N = 0, int mod = 0) :N(N), mod(mod) {
		tree.resize(N << 2);
		zero = mod ? pii(1e9, 0) : pii(0, 0);
		arr = {};
	}
	void init(int l, int r, int loc = 1) {
		if (l == r) {
			tree[loc] = arr[l];
			return;
		}
		int m = l + r >> 1;
		init(l, m, loc * 2);
		init(m + 1, r, loc * 2 + 1);
		if (mod) tree[loc] = min(tree[loc * 2], tree[loc * 2 + 1]);
		else tree[loc] = max(tree[loc * 2], tree[loc * 2 + 1]);
	}
	pii query(int s, int e, int l, int r, int loc = 1) {
		if (e < l || r < s) return zero;
		if (l <= s && e <= r) return tree[loc];
		int m = s + e >> 1;
		if (mod) return min(query(s, m, l, r, loc * 2), query(m + 1, e, l, r, loc * 2 + 1));
		else return max(query(s, m, l, r, loc * 2), query(m + 1, e, l, r, loc * 2 + 1));
	}
	pii query(int l, int r) { return query(1, N, l, r); }
};
struct query {
	int ind;
	ll U;
	int mul;
};
ll A[MAX];
ll X[MAX];
ll B[MAX];
int S[MAX];
int T[MAX];
ll U[MAX];
ll ans[MAX];
int L[MAX];
int R[MAX];
vector<int> ls[MAX];
int N, M, K;
vector<ll> Us;
segtree segA, segB;
fenwick bit;
vector<query> qv[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N >> M;
	int i;
	for (i = 1; i <= N; i++) cin >> A[i], X[i + 1] = X[i] + A[i];
	for (i = 1; i <= N; i++) cin >> B[i];
	for (i = 1; i <= M; i++) cin >> S[i] >> T[i] >> U[i], Us.push_back(U[i]);
	Us.push_back(0);
	sort(Us.begin(), Us.end());
	Us.erase(unique(Us.begin(), Us.end()), Us.end());
	K = Us.size();
	bit = fenwick(K);
	segA = segtree(N, 0);
	segB = segtree(N, 1);
	segA.arr.push_back(pii(0, 0));
	segB.arr.push_back(pii(0, 0));
	for (i = 1; i <= N; i++) segA.arr.push_back(pii(A[i], i));
	for (i = 1; i <= N; i++) segB.arr.push_back(pii(B[i], i));
	segA.init(1, N);
	segB.init(1, N);
	for (i = 1; i <= M; i++) {
		if (segA.query(S[i], T[i] - 1).first > U[i]) {
			ans[i] = -1;
			continue;
		}
		if (T[i] == N + 1) qv[S[i]].push_back({ i, U[i], 1 });
		else {
			int ind = lower_bound(X + 1, X + N + 2, X[T[i]] - U[i]) - X;
			ind = max(ind, S[i]);
			int t1 = segB.query(ind, T[i] - 1).second;
			qv[S[i]].push_back({ i, U[i], 1 });
			qv[t1].push_back({ i, U[i], -1 });
			ans[i] = X[T[i]] - X[t1];
			ans[i] *= B[t1];
		}
	}
	for (i = 1; i <= N; i++) L[i] = 0, R[i] = N + 1;
	vector<pli> st;
	st.emplace_back(0, 0);
	for (i = 1; i <= N; i++) {
		while (st.back().first > B[i]) st.pop_back();
		L[i] = st.back().second;
		st.emplace_back(B[i], i);
	}
	st.clear();
	st.emplace_back(0, N + 1);
	for (i = N; i >= 1; i--) {
		while (st.back().first >= B[i]) st.pop_back();
		R[i] = st.back().second;
		st.emplace_back(B[i], i);
	}
	for (i = 1; i <= N; i++) ls[L[i]].push_back(i);
	for (i = N; i >= 1; i--) {
		int ind = lower_bound(Us.begin(), Us.end(), X[R[i]] - X[i]) - Us.begin();
		bit.update(1, ind - 1, pll(B[i], B[i] * X[i]));
		bit.update(ind, K, pll(0, B[i] * X[R[i]]));
		bit.update(1, K, pll(0, -X[i] * B[i]));
		for (auto v : ls[i]) {
			int ind1 = lower_bound(Us.begin(), Us.end(), X[v] - X[i]) - Us.begin();
			int ind2 = lower_bound(Us.begin(), Us.end(), X[R[v]] - X[i]) - Us.begin();
			bit.update(1, K, pll(0, X[v] * B[v]));
			bit.update(1, ind1 - 1, pll(0, -B[v] * X[v]));
			bit.update(ind1, ind2 - 1, pll(-B[v], -B[v] * X[i]));
			bit.update(ind2, K, pll(0, -B[v] * X[R[v]]));
		}
		for (auto& [ind, U, mul] : qv[i]) {
			int uind = lower_bound(Us.begin(), Us.end(), U) - Us.begin();
			auto res = bit.get(uind);
			ans[ind] += mul * (res.first * U + res.second);
		}
	}
	for (i = 1; i <= M; i++) cout << ans[i] << ln;
}

Compilation message (stderr)

Main.cpp: In member function 'void segtree::init(int, int, int)':
Main.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int m = l + r >> 1;
      |           ~~^~~
Main.cpp: In member function 'pii segtree::query(int, int, int, int, int)':
Main.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |   int m = s + e >> 1;
      |           ~~^~~

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