Submission #682698

#	Time	Username	Problem	Language	Result	Execution time	Memory
682698		flappybird	Fire (JOI20_ho_t5)	C++17	1 / 100	1084 ms	52844 KiB

ho_t5

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
typedef pair<pll, pll> T;
pll operator+(pll p1, pll p2) { return pll(p1.first + p2.first, p1.second + p2.second); }
T operator+(T p1, T p2) { return T(p1.first + p2.first, p1.second + p2.second); }
pll operator-(pll p1, pll p2) { return pll(p1.first - p2.first, p1.second - p2.second); }
T operator-(T p1, T p2) { return T(p1.first - p2.first, p1.second - p2.second); }
struct fenwick {
	vector<T> tree;
	int N;
	fenwick(int N) :N(N) {
		tree.resize(N + 1);
	}
	void upd(int i, T x) {
		while (i <= N) {
			tree[i] = tree[i] + x;
			i += i & -i;
		}
	}
	T get(int i) {
		T ans({ 0, 0 }, { 0, 0 });
		while (i) {
			ans = ans + tree[i];
			i -= i & -i;
		}
		return ans;
	}
};
vector<pair<int, pll>> del[MAX];
int arr[MAX];
int l[MAX];
int r[MAX];
int last[MAX];
vector<tuple<int, int, int>> qv[MAX];
T line[MAX];
ll ans[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	int i;
	for (i = 1; i <= N; i++) cin >> arr[i];
	vector<pii> stk = { { 1e9 + 10, 0 } };
	for (i = 1; i <= N; i++) r[i] = N + 1;
	for (i = 1; i <= N; i++) {
		while (stk.back().first < arr[i]) {
			r[stk.back().second] = i;
			stk.pop_back();
		}
		l[i] = stk.back().second;
		stk.emplace_back(arr[i], i);
	}
	for (i = 1; i <= N; i++) {
		del[0].emplace_back(i, pll(1, arr[i]));
		if (l[i]) {
			del[i - l[i]].emplace_back(i, pll(-1, -arr[i]));
			del[r[i] - l[i]].emplace_back(i, pll(1, arr[i]));
		}
		del[r[i] - i].emplace_back(i, pll(-1, -arr[i]));
	}
	int low, high, t;
	for (i = 1; i <= Q; i++) {
		cin >> t >> low >> high;
		qv[t].emplace_back(low, high, i);
	}
	fenwick bit(N);
	auto get = [&](int i, int t) {
		if (i < 1) return 0ll;
		int l, r;
		l = 0;
		r = N + 1;
		while (r - l > 1) {
			int mid = (l + r) / 2;
			auto res = bit.get(mid);
			if (t * res.first.first + res.first.second > i) r = mid;
			else l = mid;
		}
		auto res = bit.get(l);
		int ind = t * res.first.first + res.first.second;
		return 1ll * arr[l + 1] * (i - res.first.first * t - res.first.second) + res.second.first * t + res.second.second;
	};
	for (i = 0; i <= N; i++) {
		for (auto& [loc, p] : del[i]) {
			T pv = line[loc];
			auto& [a, b] = line[loc].first;
			auto& [c, d] = line[loc].second;
			a = line[loc].first.first;
			b = line[loc].first.second;
			ll y = a * i + b;
			y += p.first;
			a += p.first;
			b = y - a * i;
			c = line[loc].second.first;
			d = line[loc].second.second;
			y = c * i + d;
			y += p.second;
			c += p.second;
			d = y - c * i;
			bit.upd(loc, line[loc] - pv);
		}
		for (auto& [l, r, n] : qv[i]) ans[n] = get(r, i) - get(l - 1, i);
	}
	for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}

Compilation message (stderr)

ho_t5.cpp: In lambda function:
ho_t5.cpp:92:7: warning: unused variable 'ind' [-Wunused-variable]
   92 |   int ind = t * res.first.first + res.first.second;
      |       ^~~

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