oj.uz

Submission #697729

# Submission time Handle Problem Language Result Execution time Memory
697729 2023-02-10T22:51:57 Z flappybird Dungeon 3 (JOI21_ho_t5) C++17
100 / 100
 614 ms 71448 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10452 KB Output is correct
2 Correct 10 ms 10708 KB Output is correct
3 Correct 10 ms 10708 KB Output is correct
4 Correct 11 ms 10620 KB Output is correct
5 Correct 12 ms 10680 KB Output is correct
6 Correct 10 ms 10680 KB Output is correct
7 Correct 10 ms 10548 KB Output is correct
8 Correct 9 ms 10708 KB Output is correct
9 Correct 10 ms 10600 KB Output is correct
10 Correct 10 ms 10580 KB Output is correct
11 Correct 10 ms 10680 KB Output is correct
12 Correct 10 ms 10660 KB Output is correct
13 Correct 12 ms 10580 KB Output is correct
14 Correct 10 ms 10708 KB Output is correct
15 Correct 13 ms 10724 KB Output is correct
16 Correct 10 ms 10708 KB Output is correct
17 Correct 10 ms 10488 KB Output is correct
18 Correct 11 ms 10580 KB Output is correct
19 Correct 9 ms 10580 KB Output is correct
20 Correct 9 ms 10656 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 22068 KB Output is correct
2 Correct 101 ms 23280 KB Output is correct
3 Correct 92 ms 24796 KB Output is correct
4 Correct 90 ms 23628 KB Output is correct
5 Correct 85 ms 23128 KB Output is correct
6 Correct 453 ms 65060 KB Output is correct
7 Correct 474 ms 62544 KB Output is correct
8 Correct 441 ms 70208 KB Output is correct
9 Correct 471 ms 66144 KB Output is correct
10 Correct 495 ms 68752 KB Output is correct
11 Correct 506 ms 68080 KB Output is correct
12 Correct 488 ms 65268 KB Output is correct
13 Correct 435 ms 61900 KB Output is correct
14 Correct 444 ms 61244 KB Output is correct
15 Correct 240 ms 66464 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 52624 KB Output is correct
2 Correct 330 ms 58944 KB Output is correct
3 Correct 338 ms 54388 KB Output is correct
4 Correct 343 ms 52552 KB Output is correct
5 Correct 303 ms 53736 KB Output is correct
6 Correct 320 ms 57748 KB Output is correct
7 Correct 363 ms 50368 KB Output is correct
8 Correct 297 ms 55692 KB Output is correct
9 Correct 287 ms 51916 KB Output is correct
10 Correct 182 ms 55064 KB Output is correct
11 Correct 373 ms 52132 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10452 KB Output is correct
2 Correct 10 ms 10708 KB Output is correct
3 Correct 10 ms 10708 KB Output is correct
4 Correct 11 ms 10620 KB Output is correct
5 Correct 12 ms 10680 KB Output is correct
6 Correct 10 ms 10680 KB Output is correct
7 Correct 10 ms 10548 KB Output is correct
8 Correct 9 ms 10708 KB Output is correct
9 Correct 10 ms 10600 KB Output is correct
10 Correct 10 ms 10580 KB Output is correct
11 Correct 10 ms 10680 KB Output is correct
12 Correct 10 ms 10660 KB Output is correct
13 Correct 12 ms 10580 KB Output is correct
14 Correct 10 ms 10708 KB Output is correct
15 Correct 13 ms 10724 KB Output is correct
16 Correct 10 ms 10708 KB Output is correct
17 Correct 10 ms 10488 KB Output is correct
18 Correct 11 ms 10580 KB Output is correct
19 Correct 9 ms 10580 KB Output is correct
20 Correct 9 ms 10656 KB Output is correct
21 Correct 88 ms 22068 KB Output is correct
22 Correct 101 ms 23280 KB Output is correct
23 Correct 92 ms 24796 KB Output is correct
24 Correct 90 ms 23628 KB Output is correct
25 Correct 85 ms 23128 KB Output is correct
26 Correct 453 ms 65060 KB Output is correct
27 Correct 474 ms 62544 KB Output is correct
28 Correct 441 ms 70208 KB Output is correct
29 Correct 471 ms 66144 KB Output is correct
30 Correct 495 ms 68752 KB Output is correct
31 Correct 506 ms 68080 KB Output is correct
32 Correct 488 ms 65268 KB Output is correct
33 Correct 435 ms 61900 KB Output is correct
34 Correct 444 ms 61244 KB Output is correct
35 Correct 240 ms 66464 KB Output is correct
36 Correct 399 ms 52624 KB Output is correct
37 Correct 330 ms 58944 KB Output is correct
38 Correct 338 ms 54388 KB Output is correct
39 Correct 343 ms 52552 KB Output is correct
40 Correct 303 ms 53736 KB Output is correct
41 Correct 320 ms 57748 KB Output is correct
42 Correct 363 ms 50368 KB Output is correct
43 Correct 297 ms 55692 KB Output is correct
44 Correct 287 ms 51916 KB Output is correct
45 Correct 182 ms 55064 KB Output is correct
46 Correct 373 ms 52132 KB Output is correct
47 Correct 614 ms 63908 KB Output is correct
48 Correct 603 ms 71448 KB Output is correct
49 Correct 589 ms 66360 KB Output is correct
50 Correct 604 ms 65640 KB Output is correct
51 Correct 585 ms 65968 KB Output is correct
52 Correct 613 ms 70088 KB Output is correct
53 Correct 570 ms 61748 KB Output is correct
54 Correct 538 ms 67860 KB Output is correct
55 Correct 569 ms 63624 KB Output is correct
56 Correct 288 ms 65688 KB Output is correct
57 Correct 514 ms 63220 KB Output is correct