| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 651179 | bicsi | Fire (JOI20_ho_t5) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q; cin >> n >> q;
vector<int> v(n);
for (int i = 0; i < n; ++i) cin >> v[i];
vector<int> len[2];
for (int rev = 0; rev < 2; ++rev) {
vector<int> stk = {-1};
for (int i = 0; i < n; ++i) {
while (stk.size() > 1 && v[i] + rev > v[stk.back()])
stk.pop_back();
len[rev].push_back(i - stk.back());
stk.push_back(i);
}
reverse(v.begin(), v.end());
}
reverse(len[1].begin(), len[1].end());
int t = 0;
auto get_range = [&](int i) {
int l = len[0][i] > i ? i : i + max(0, t - len[0][i] + 1);
int r = i + min(t + 1, len[1][i]);
return make_pair(l, r);
};
auto cmp = [&](int i, int j) {
assert(i >= 0);
if (j < 0) {
auto [l, r] = get_range(i);
return r < (~j);
}
return i < j;
};
set<int, decltype(cmp)> S(cmp);
for (int i = 0; i < n; ++i)
S.insert(i);
vector<pair<int, long long>> fw(n + 1);
auto update = [&](int i, int k, long long c) {
for (++i; i <= n; i += (i & -i)) {
fw[i].first += k;
fw[i].second += c;
}
};
auto query = [&](int pos) {
int i = *S.lower_bound(~pos);
auto [l, r] = get_range(i);
assert(l <= pos && r >= pos);
long long ans = 1LL * (min(r, pos) - l) * v[i];
for (; i > 0; i -= (i & -i))
ans += 1LL * fw[i].first * t + fw[i].second;
return ans;
};
for (int i = 0; i < n; ++i)
update(i, v[i], v[i]);
vector<tuple<int, int, int>> evs;
for (int i = 0; i < n; ++i) {
evs.emplace_back(len[1][i] - 1, 0, i);
if (len[0][i] <= i) {
evs.emplace_back(len[0][i] - 1, 0, i);
evs.emplace_back(len[0][i] + len[1][i] - 1, 1, i);
}
}
vector<pair<int, int>> qs(q);
for (int i = 0; i < q; ++i) {
int t, l, r; cin >> t >> l >> r;
qs[i] = {l - 1, r};
evs.emplace_back(t, 2, i);
}
sort(evs.begin(), evs.end());
vector<long long> ans(q);
for (auto& [t_, typ, i] : evs) {
t = t_;
if (typ == 0) { // decrease slope
update(i, -v[i], 1LL * t * v[i]);
} else if (typ == 1) { // erase
S.erase(i);
update(i, v[i], -1LL * t * v[i]);
} else { // query
auto [l, r] = qs[i];
ans[i] = query(r) - query(l);
}
}
for (int i = 0; i < q; ++i)
cout << ans[i] << '\n';
return 0;
}