Submission #237134

#	Time	Username	Problem	Language	Result	Execution time	Memory
237134		islingr	Fire (JOI20_ho_t5)	C++14	100 / 100	604 ms	41724 KiB

ho_t5

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define trav(x, v) for (auto &x : v)
#define eb(x...) emplace_back(x)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)

using ll = int64_t;

struct S {
	int n; vector<ll> t;
	S(int n = 0) : n{n}, t(2 * n, 0) { } 
	ll query(int r) {
		ll s = 0; int l = n;
		for (r += n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) s += t[l++];
			if (r & 1) s += t[--r];
		}
		return s;
	}
	void add(int p, ll v) {
		for (t[p += n] += v; p >>= 1; )
			t[p] = t[p << 1|0] + t[p << 1|1];
	}
};

const int N = 13 << 14;
int s[N], p[N], nxt[N], t[N];
ll ans[N], pref[N];
vector<int> e[N], g[N];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m; cin >> n >> m;
	rep(i, 1, n) {
		cin >> s[i];
		pref[i] = pref[i - 1] + s[i];

		p[i] = i - 1; nxt[i] = n + 1;
		while (p[i] && s[p[i]] < s[i])
			nxt[p[i]] = i, p[i] = p[p[i]];
	}
	rep(i, 1, n) if (!p[i]) p[i] = i;

	rep(i, 1, m) {
		int l, r; cin >> t[i] >> l >> r;
		e[l - 1].eb(-i); e[r].eb(i);
	}

	vector<int> a;
	rep(i, 1, n) {
		while(!a.empty() && s[a.back()] < s[i]) a.pop_back();
		a.eb(i);
		trav(j, e[i]) {
			int prev = *lb(all(a), i - t[abs(j)]);
			ll del = 1ll * s[prev] * (i - prev) + pref[prev];
			if (j < 0) ans[-j] -= del;
			else ans[j] += del;
			g[prev].eb(j);
		}
	}

	S U(n), US(n), D(n), DS(n);
	rep(i, 1, n) {
		ll w = s[p[i]] - s[i];
		int u = i - p[i] - 1, d = nxt[i] - p[i] - 1;
		US.add(u, w * u); U.add(u, w);
		DS.add(d, w * d); D.add(d, w);
		trav(j, g[i]) {
			int t = ::t[abs(j)];
			ll del = 0;
			del += U.query(t) * t - US.query(t);
			del += DS.query(t) - D.query(t) * t;
			if (j < 0) ans[-j] -= del;
			else ans[j] += del;
		}
	}

	rep(i, 1, m) cout << ans[i] << '\n';	
}

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