Submission #1313327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313327		nicolo_010	Fire (JOI20_ho_t5)	C++20	7 / 100	111 ms	6276 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define f first
#define s second

struct SegTree {
	vector<int> tree;
	SegTree(int n) {
		tree.assign(4*n, 0);
	}

	void query(int p, int l, int r,int i, int x) {
		if (l>i || r<i) return;
		if (l==r) {
			tree[p] = x;
			return;;
		}
		else {
			int m = (l+r)/2;
			query(2*p, l, m, i, x);
			query(2*p+1, m+1, r, i, x);
			int i1 = tree[2*p];
			int i2 = tree[2*p+1];
			tree[p] = max(i1, i2);
		}
	}

	int rmq(int p, int l, int r, int i, int j) {
		if (l> j || r < i) return 0;
		if (i <= l && r <= j) return tree[p];
		int m = (l+r)/2;
		int i1 = rmq(2*p, l, m, i, j);
		int i2 = rmq(2*p+1, m+1, r, i, j);
		return max(i1, i2);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, q; cin >> n >> q;
	vector<int> a(n);
	SegTree st(n);
	for (int i=0; i<n; i++) {
		cin >> a[i];
		st.query(1, 0, n-1, i, a[i]);
	}
	while (q--) {
		int t, l, r; cin >> t >> l >> r;
		l--; r--;
		cout << st.rmq(1, 0, n-1, max(0, l-t), l) << '\n';
	}
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80