Submission #1313331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313331		nicolo_010	Fire (JOI20_ho_t5)	C++20	6 / 100	184 ms	36040 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

vector<int> a;
struct SegTree {
	struct Node {
		int L=-1, R=-1;
		int val=0;
	};
	vector<Node> tree;

	SegTree(int n) {
		tree.reserve(20*n);
		build(0, n-1);
	}
	int build(int l, int r) {
		tree.push_back({});
		int p = tree.size()-1;
		if (l==r) {
			tree[p].val = a[l];
			return p;
		}
		int m = (l+r)/2;
		int i1 = build(l, m);
		int i2 = build(m+1, r);
		tree[p].val = tree[i1].val + tree[i2].val;
		tree[p].L = i1;
		tree[p].R = i2;
		return p;
	}

	int update(int p, int l, int r, int i) {
		tree.push_back(tree[p]);
		int cur = tree.size()-1;
		if (l==r) {
			tree[cur].val = tree[p].val+1;
			return cur;
		}
		int m = (l+r)/2;
		if (i<=m) {
			tree[cur].L = update(tree[p].L, l, m, i);
		}
		else {
			tree[cur].R = update(tree[p].R, m+1, r, i);
		}
		int i1 = tree[cur].L;
		int i2 = tree[cur].R;
		tree[cur].val = tree[i1].val + tree[i2].val;
		return cur;
	}

	int rsq(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].val;
		int m = (l+r)/2;
		int i1 = rsq(tree[p].L, l, m, i, j);
		int i2 = rsq(tree[p].R, m+1, r, i, j);
		return i1+i2;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, q; cin >> n >> q;
	a.assign(n, 0);
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}
	SegTree st(n);
	vector<vector<int>> ti(n+1);
	vector<int> root(n+1);
	root[0] = 0;
	vector<int> last(n, -1);
	if (a[0]==2) last[0] = 0;
	for (int i=1; i<n; i++) {
		if (a[i]==2) last[i] = i;
		else last[i] = last[i-1];
		if (last[i] != -1) ti[i-last[i]].push_back(i);
	}

	for (int t=1; t<=n; t++) {
		int r=root[t-1];
		for (auto x : ti[t]) {
			r = st.update(r, 0, n-1, x);
		}
		root[t] = r;
	}

	while (q--) {
		int t, l, r; cin >> t >> l >> r;
		l--; r--;
		cout << st.rsq(root[t], 0, n-1, l, r) << "\n";
	}
}

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