| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 203435 | Bruteforceman | Fire (JOI20_ho_t5) | C++11 | 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>
using namespace std;
#define prev previous
const int maxn = 200005;
using pii = pair <int, int>;
int n;
int s[maxn];
struct query {
int l, r, t;
} Q[maxn];
vector <int> v[maxn];
int prev[maxn];
vector <int> g[maxn];
int sub[maxn];
long long pred[maxn];
long long pref[maxn];
long long res[maxn];
vector <int> h[maxn];
void eulerOrder(int x) {
for(int i : g[x]) {
eulerOrder(i);
pred[i] = sub[x];
sub[x] += sub[i];
}
sub[x] += 1;
}
struct BinaryIndexedTree {
long long t[maxn];
int size;
void update(int x, long long val) {
x += 1;
for(int i = x; i <= size + 1; i += i & (-i)) {
t[i] += val;
}
}
long long sum(int x) {
x = min(x, size);
x += 1;
long long ans = 0;
for(int i = x; i > 0; i -= i & (-i)) {
ans += t[i];
}
return ans;
}
};
int main() {
int q;
scanf("%d %d", &n, &q);
for_each(s + 1, s + n + 1, [] (int &i) { scanf("%d", &i); });
for_each(Q + 1, Q + q + 1, [&] (query &i) {
scanf("%d %d %d", &i.t, &i.l, &i.r); });
for(int i = 1; i <= q; i++) {
v[Q[i].l - 1].push_back(-i);
v[Q[i].r].push_back(i);
}
for(int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] + s[i];
}
stack <int> st;
for(int i = 1; i <= n; i++) {
while(!st.empty() && s[st.top()] < s[i]) {
st.pop();
}
prev[i] = st.empty() ? 0 : st.top();
st.push(i);
}
for(int i = 1; i <= n; i++) {
g[prev[i]].push_back(i);
}
eulerOrder(0);
auto cost = [&] (int &x) {
if(prev[x] == 0) return 0;
else return s[prev[x]] - s[x];
};
BinaryIndexedTree A, B, C, D;
A.size = B.size = C.size = D.size = n;
vector <int> rmq;;
for(int i = 1; i <= n; i++) {
while(!rmq.empty() && s[rmq.back()] < s[i]) {
rmq.pop_back();
}
rmq.push_back(i);
for(auto j : v[i]) {
int id = j;
int t = Q[abs(id)].t;
int last = *lower_bound(rmq.begin(), rmq.end(), i - t);
long long add = 1LL * s[last] * (i - last) + pref[last];
h[last].emplace_back(id);
if(id < 0) res[-id] -= add;
else res[id] += add;
}
}
for(int i = 1; i <= n; i++) {
int k = i;
A.update(pred[k], 1LL * cost(k) * pred[k]);
B.update(pred[k], 1LL * cost(k));
C.update(pred[k] + sub[k], 1LL * cost(k) * (sub[k] + pred[k]));
D.update(pred[k] + sub[k], 1LL * cost(k));
for(auto j : h[i]) {
int id = j;
int t = Q[abs(id)].t;
long long add = 0;
add += B.sum(t) * t - A.sum(t);
add += C.sum(t) - D.sum(t) * t;
if(id < 0) res[-id] -= add;
else res[id] += add;
}
}
for_each(res + 1, res + q + 1, [] (auto &i) { printf("%lld\n", i); } );
return 0;
}