Submission #237181

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
237181	2020-06-05T06:23:23 Z	islingr	Fire (JOI20_ho_t5)	C++14	Compilation error	0 ms	0 KB

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];
vector<int> q[N], e[N];

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

	int n, m; cin >> n >> m;
	rep(i, 1, n) {
		cin >> 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;
		q[l - 1].eb(-i); q[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, q[i]) {
			int prev = *lb(all(a), i - t[abs(j)]);
			ll del = 1ll * s[prev] * (i - prev);
			if (j < 0) ans[-j] -= del;
			else ans[j] += del;
			g[prev].eb(j);
		}
	}

	S U(n), US(n), D(n), DS(n); ll sum = 0;
	rep(i, 1, n) {
		ll w = s[p[i]] - s[i]; sum += 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, e[i]) {
			int t = ::t[abs(j)];
			ll del = sum;
			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';	
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:63:4: error: 'g' was not declared in this scope
    g[prev].eb(j);
    ^