Submission #201600

#	Time	Username	Problem	Language	Result	Execution time	Memory
201600		Noam527	Fire (JOI20_ho_t5)	C++17	100 / 100	420 ms	84368 KiB

ho_t5

#include <bits/stdc++.h>
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 4e18;
const int OO = 1;
const int OOO = 1;
using namespace std;

struct fenwick {
	int n;
	vector<ll> t;
	fenwick() {}
	fenwick(int sz) {
		n = sz;
		t.resize(n + 1, 0);
	}
	void clear() {
		for (auto &i : t) i = 0;
	}
	void add(int x, ll v) {
		for (x++; x <= n; x += (x & -x)) t[x] += v;
	}
	ll query(int x) {
		ll rtn = 0;
		for (x++; x; x ^= (x & -x)) rtn += t[x];
		return rtn;
	}
	ll query(int l, int r) {
		return query(r) - query(l - 1);
	}
};

struct query {
	int l, r, i;
	query() {}
	query(int _l, int _r, int _i) {
		l = _l;
		r = _r;
		i = _i;
	}
};

struct eve {
	int i;
	ll v;
	eve(int _i, ll _v) {
		i = _i;
		v = _v;
	}
};

const int N = 2e5 + 5;

int n, q;
vector<int> s, L, R;

vector<query> que[N];
vector<ll> ans;

vector<eve> line[N], diag[N];
fenwick f;

void addline(int x, int y, int len, ll v) {
	line[x].push_back(eve(y, v));
	if (x + len <= n)
		line[x + len].push_back(eve(y, -v));
}
void adddiag(int x, int y, int len, ll v) {
	y = y - x + n;
	diag[x].push_back(eve(y, v));
	if (x + len <= n)
		diag[x + len].push_back(eve(y, -v));
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> q;
	s.resize(n), L.resize(n), R.resize(n);
	ans.resize(q, 0);
	f = fenwick(2 * n);

	for (auto &i : s) cin >> i;
	for (int i = 0, t, l, r; i < q; i++) {
		cin >> t >> l >> r;
		--l, --r;
		que[t].push_back(query(l, r, i));
	}

	vector<pair<int, int>> st;
	st.emplace_back(md, -md);
	for (int i = 0; i < n; i++) {
		while (st.back().first <= s[i]) st.pop_back();
		L[i] = st.back().second;
		st.emplace_back(s[i], i);
	}
	st.clear(), st.emplace_back(md, n);
	for (int i = n - 1; i >= 0; i--) {
		while (s[i] > st.back().first) st.pop_back();
		R[i] = st.back().second;
		st.emplace_back(s[i], i);
	}
	for (int i = 0; i < n; i++) {
		if (i - L[i] < R[i] - i) {
			// diagonal
			for (int j = 0; j < i - L[i]; j++)
				adddiag(j, i, R[i] - i, s[i]);
		}
		else {
			// horizontal
			for (int j = 0; j < R[i] - i; j++)
				addline(j, i + j, i - L[i], s[i]);
		}
	}

	// diagonal sweepline
	for (int t = 0; t <= n; t++) {
		for (const auto &i : diag[t])
			f.add(i.i, i.v);
		for (const auto &i : que[t])
			ans[i.i] += f.query(i.l - t + n, i.r - t + n);
	}
	f.clear();
	// horizontal sweepline
	for (int t = 0; t <= n; t++) {
		for (const auto &i : line[t])
			f.add(i.i, i.v);
		for (const auto &i : que[t])
			ans[i.i] += f.query(i.l, i.r);
	}
	for (const auto &i : ans) cout << i << '\n';
}

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