Submission #518800

#	Time	Username	Problem	Language	Result	Execution time	Memory
518800		HynDuf	Fire (JOI20_ho_t5)	C++11	100 / 100	557 ms	164444 KiB

ho_t5

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; FOR(_, l, r) DB1(A, _); cerr << '\n';}
#define sz(x) ((int) (x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;

typedef pair<ll, int> ii;
typedef array<int, 3> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vl;
template<typename T>
struct FT {
	vector<T> fenw;
	FT() {}
	FT(int N) : fenw(N + 1, 0) {}
	void upd(int x, T v) {
		// case x < 1?
		assert(x > 0);
		for (; x < sz(fenw); x += x & -x) {
			fenw[x] += v;
		}
	}
	T query(int x) {
		// case x >= sz(fenw)?
		assert(x < sz(fenw));
		T ans = 0;
		for (; x > 0; x -= x & -x) ans += fenw[x];
		return ans;
	}
	T query(int l, int r) {
		return query(r) - query(l - 1);
	}
};
const int N = 2e5 + 2;
int n, q, s[N];
ll ans[N];
viii qu[N];
vii upd_list[N][6]; // {v, pos}
FT<ll> fw[6];
// fw[0] ~ sum of v of open segments (to do: cur_time*sum_v - (0 - 1)*v) ~ all segments start at time 0
// fw[1] ~ sum of (left-1)*v of open segments (to do: pos*sum_v -(left - 1)*v)
// fw[2] ~ sum of (left-1)*v of closed segments
// fw[3] ~ sum of v of left closed segments
// fw[4] ~ sum of right*v of closed segments
// fw[5] ~ sum of v of right closed segments
void push_upd_events(int l, int r, int v)
{
	if (l > r) return;
	assert(l >= 1 && r <= 2 * n);
	upd_list[0][0].pb({v, l});
	upd_list[0][1].pb({(l - 1) * 1LL * v, l});
	int end_time = r - l + 1;
	upd_list[end_time][0].pb({-v, l});
	upd_list[end_time][1].pb({-(l - 1) * 1LL * v, l});
	upd_list[end_time][2].pb({(l - 1) * 1LL * v, l});
	upd_list[end_time][3].pb({v, l});
	upd_list[end_time][4].pb({r * 1LL * v, r});
	upd_list[end_time][5].pb({v, r});

}
void push_raw_upd_events(int l, int r, int t, int v)
{
	l += n, r += n;
	int L = l - t;
	push_upd_events(L, l - 1, -v);
	push_upd_events(L, r, v);
}
int D[N], top, right[N];
void build_upd_list()
{
	FOR(i, 0, 5) fw[i] = FT<ll> (2 * n);
	D[0] = n + 1;
	FORD(i, n, 1)
	{
		while (top && s[D[top]] < s[i]) 
		{
			push_raw_upd_events(D[top], right[D[top]], D[top] - i, -s[D[top]]);
			top--;
		}
		right[i] = D[top] - 1;
		push_raw_upd_events(i, right[i], 0, s[i]);
		D[++top] = i;
	}
}
ll cal(int pos, int cur_time)
{
	if (pos == 0) return 0;
	pos += n;
	ll res = 0;
	// open segments
	ll sum_v = fw[0].query(pos - cur_time);
	res += sum_v * (cur_time + 1);
	ll sum_left = fw[1].query(pos - cur_time + 1, pos);
	sum_v = fw[0].query(pos - cur_time + 1, pos);
	res += pos * sum_v - sum_left;
	// close segments
	sum_v = fw[3].query(pos);
	sum_left = fw[2].query(pos);
	res += pos * sum_v - sum_left;
	sum_v = fw[5].query(pos);
	ll sum_right = fw[4].query(pos);
	res += sum_right - pos * sum_v;
	return res;
}
int main()
{
#ifdef HynDuf
	freopen("inp.txt", "r", stdin);
#else
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
	cin >> n >> q;
	FOR(i, 1, n) cin >> s[i];
	FOR(i, 1, q)
	{
		int l, r, t;
		cin >> t >> l >> r;
		qu[t].pb({l, r, i});
	}
	build_upd_list();
	FOR(cur_time, 0, n)
	{
		FOR(i, 0, 5) for (ii &v : upd_list[cur_time][i]) fw[i].upd(v.S, v.F);
		for (auto &Q : qu[cur_time]) ans[Q[2]] = cal(Q[1], cur_time) - cal(Q[0] - 1, cur_time);
	}
	FOR(i, 1, q) 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