Submission #455251

#	Time	Username	Problem	Language	Result	Execution time	Memory
455251		valerikk	Fire (JOI20_ho_t5)	C++17	100 / 100	485 ms	115968 KiB

ho_t5

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <random>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const int N = 400010;

struct Fenwick {
	int n;
	vector<ll> f;

	void upd(int ind, int d) {
		for (int i = ind + 1; i <= n; i += i & -i) {
			f[i] += d;
		}
	}

	ll get(int r) {
		ll sum = 0;
		for (int i = r; i > 0; i -= i & -i) {
			sum += f[i];
		}
		return sum;
	}

	ll get(int l, int r) {
		if (l >= r) {
			return 0;
		}
		return get(r) - get(l);
	}

	Fenwick(int n_ = 0) : n(n_) {
		f.assign(n + 1, 0ll);
	}
};

int n, q;
int s[N];
int t[N], L[N], R[N];
vector<int> by_t[N];
ll ans[N];
pair<int, int> mx[2 * N];
vector<pair<int, int>> updl[N], updr[N];
Fenwick fl, fr;

void add(int l, int r, int ind, int d, int type) {
	if (type == 0) {
		updl[l].push_back({ind, d});
		updl[r + 1].push_back({ind, -d});
	} else {
		updr[l].push_back({ind, d});
		updr[r + 1].push_back({ind, -d});
	}
}

pair<int, int> get_max(int l, int r) {
	l += n, r += n;
	pair<int, int> res = {-INF, -INF};
	while (l < r) {
		if (l & 1) {
			res = max(res, mx[l]);
			++l;
		}
		if (r & 1) {
			--r;
			res = max(res, mx[r]);
		}
		l >>= 1, r >>= 1;
	}
	return res;
}

void rec(int l, int r) {
	if (l > r) {
		return;
	}
	int m = get_max(l, r + 1).second;
	rec(l, m - 1);
	rec(m + 1, r);
	if (m - l < r - m) {
		for (int i = l; i <= m; ++i) {
			add(m - i + 1, r - i + 1, i, s[m], 0);
		}
	} else {
		for (int i = m; i <= r; ++i) {
			add(i - m + 1, i - l + 1, i, s[m], 1);
		}
	}
} 

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	for (int i = 0; i < n; ++i) {
		s[i + n] = s[i];
		s[i] = -INF;
	}
	for (int i = 0; i < q; ++i) {
		cin >> t[i] >> L[i] >> R[i];
		--L[i];
		++t[i];
		L[i] += n, R[i] += n;
		by_t[t[i]].push_back(i);
	}
	n *= 2;
	for (int i = 0; i < n; ++i) {
		mx[i + n] = {s[i], i};
	}
	for (int i = n - 1; i > 0; --i) {
		mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
	}
	rec(0, n - 1);
	fl = fr = Fenwick(n);
	for (int t = 1; t <= n; ++t) {
		for (auto [ind, d] : updl[t]) {
			fl.upd(ind, d);
		}
		for (auto [ind, d] : updr[t]) {
			fr.upd(ind, d);
		}
		for (int i : by_t[t]) {
			ans[i] += fr.get(L[i], R[i]);
			ans[i] += fl.get(L[i] - t + 1, R[i] - t + 1);
		}
	}
	for (int i = 0; i < q; ++i) {
		cout << ans[i] << "\n";
	}
	return 0;
}

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