#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(x, a) for (const auto& x: a)
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int inf = 1e9 + 7;
int nxL[N], nxH[N];
array<int,3> arr[N];
vector<array<int,3>> upd[N];
ll ans[N];
struct segment_tree {
struct data {
ll s=0, l=1;
data() {}
data(ll s, ll l) : s(s), l(l) {}
};
typedef ll operation;
static data combine(data dl, data dr) {
return {dl.s + dr.s, dl.l + dr.l};
}
static data calculate(operation o, data d) {
return {o * d.l + d.s, d.l};
}
static operation merge(operation ot, operation ob) {
return ot + ob;
}
int n, h;
vector<data> t;
vector<operation> o;
segment_tree(int n = 0) : n(n), h(32 - __builtin_clz(n)), t(2 * n), o(n) {
for (int i = 0; i < n; i++)
t[i + n] = {0, 1};
for (int x = n - 1; x > 0; x--)
t[x] = combine(t[x << 1], t[x << 1 | 1]);
}
segment_tree(vector<data> & a) : segment_tree(a.size()) {
for (int i = 0; i < n; i++)
t[i + n] = a[i];
for (int x = n - 1; x > 0; x--)
t[x] = combine(t[x << 1], t[x << 1 | 1]);
}
void apply(int x, operation op) {
t[x] = calculate(op, t[x]);
if (x < n)
o[x] = merge(op, o[x]);
}
void push(int x) {
for (int s = h; s > 0; s--) {
int c = x >> s;
apply(c << 1, o[c]);
apply(c << 1 | 1, o[c]);
o[c] = operation();
}
}
void build(int x) {
while (x >>= 1)
t[x] = calculate(o[x], combine(t[x << 1], t[x << 1 | 1]));
}
// set the data at the position i
void setValue(int i, data d) {
i += n;
push(i);
t[i] = d;
build(i);
}
// query the data on the range [l, r[
ll query(int l, int r) {
l += n; r += n;
push(l); push(r - 1);
data dl, dr;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1)
dl = combine(dl, t[l++]);
if (r & 1)
dr = combine(t[--r], dr);
}
return combine(dl, dr).s;
}
// apply an operation on the range [l, r[
void apply(int l, int r, operation op) {
l += n; r += n;
push(l); push(r - 1);
int xl = l, xr = r;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1)
apply(l++, op);
if (r & 1)
apply(--r, op);
}
build(xl); build(xr - 1);
}
};
#define log2(x) (31 - __builtin_clz(x))
struct sparse_table {
int n;
vector<segment_tree::data> a;
vector<vector<int>> st;
int combine(int dl, int dr) {
return a[dl].s > a[dr].s ? dl : dr;
}
sparse_table() {}
sparse_table(vector<segment_tree::data> & a) : n(a.size()), a(a), st(log2(n) + 1, vector<int>(n)) {
for (int i = 0; i < n; i++)
st[0][i] = i;
for (int j = 1; 1 << j <= n; j++)
for (int i = 0; i + (1 << j) <= n; i++)
st[j][i] = combine(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
// query the data on the range [l, r[
int query(int l, int r) {
int s = log2(r - l);
return combine(st[s][l], st[s][r - (1 << s)]);
}
};
int main() {
int n, q; scanf("%d %d", &n, &q);
int n2 = n+2;
while (n2 & (n2-1)) n2++;
vector<segment_tree::data> s(n2);
s[0] = s[n+1] = {inf, 1};
for (int i = 1; i <= n; i++) {
scanf("%I64d", &s[i].s);
s[i].l = 1;
}
stack<int> st; st.push(n+1);
for (int i = n; i; i--) {
while (!st.empty() && s[st.top()].s < s[i].s)
st.pop();
nxH[i] = st.top();
st.push(i);
}
while (!st.empty()) st.pop();
st.push(0);
for (int i = 1; i <= n; i++) {
while (!st.empty() && s[st.top()].s < s[i].s)
st.pop();
nxL[i] = st.top();
st.push(i);
}
sparse_table sp(s);
segment_tree f(n2);
for (int i = 1; i <= n; i++) {
if (i+1 <= nxH[i]-1) {
int v = s[i].s - s[sp.query(i+1, nxH[i])].s;
f.apply(i, n+1, v);
upd[nxH[i]-i].pb({i+1, nxH[i]-1, v});
}
if (nxL[i]+1 <= i-1 && nxL[i] != 0 && s[nxL[i]].s != s[i].s) {
int v = s[i].s - s[sp.query(nxL[i]+1, i)].s;
f.apply(nxL[i], n+1, v);
upd[i-nxL[i]].pb({nxL[i]+1, i-1, v});
}
}
segment_tree seg(s);
for (int i = 0; i < q; i++) {
for (int j = 0; j < 3; j++)
scanf("%d", &arr[i][j]);
upd[arr[i][0]].pb({-i, arr[i][1], arr[i][2]});
}
for (int i = 1; i <= n; i++) {
trav(j, upd[i]) {
if (j[0] > 0) {
seg.apply(j[0], j[1]+1, j[2]);
f.apply(j[0]-1, n+1, -j[2]);
}
}
trav(j, upd[i]) {
if (j[0] <= 0) {
ans[-j[0]] = seg.query(j[1], j[2]+1);
ans[-j[0]] += f.query(max(0,j[2]-i), j[2]-1+1) - f.query(max(0,j[1]-i-1), max(0,j[1]-2)+1);
}
}
}
for (int i = 0; i < q; i++)
printf("%I64d\n", ans[i]);
}
Compilation message
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:132:27: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
scanf("%I64d", &s[i].s);
~~~~~~~^
ho_t5.cpp:185:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
printf("%I64d\n", ans[i]);
~~~~~~^
ho_t5.cpp:126:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, q; scanf("%d %d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%I64d", &s[i].s);
~~~~~^~~~~~~~~~~~~~~~~~
ho_t5.cpp:167:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &arr[i][j]);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4980 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4980 KB |
Output is correct |
| 2 |
Execution timed out |
1022 ms |
77944 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4980 KB |
Output is correct |
| 2 |
Execution timed out |
1000 ms |
78960 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
781 ms |
76620 KB |
Output is correct |
| 2 |
Correct |
771 ms |
76492 KB |
Output is correct |
| 3 |
Correct |
785 ms |
76996 KB |
Output is correct |
| 4 |
Correct |
783 ms |
77272 KB |
Output is correct |
| 5 |
Correct |
769 ms |
77012 KB |
Output is correct |
| 6 |
Correct |
770 ms |
76364 KB |
Output is correct |
| 7 |
Correct |
774 ms |
76612 KB |
Output is correct |
| 8 |
Correct |
769 ms |
76868 KB |
Output is correct |
| 9 |
Correct |
775 ms |
76888 KB |
Output is correct |
| 10 |
Correct |
770 ms |
76488 KB |
Output is correct |
| 11 |
Correct |
781 ms |
77264 KB |
Output is correct |
| 12 |
Correct |
789 ms |
77136 KB |
Output is correct |
| 13 |
Correct |
786 ms |
77004 KB |
Output is correct |
| 14 |
Correct |
794 ms |
77136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4980 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
5112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
