#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define pii pair < int, pi >
#define next next123
#define add add123
const int N = 2e5 + 7;
const int INF = 1e9 + 7;
pair < pi, pi > qr[N];
ll s[4][4 * N], v3[4 * N], lz[4 * N], ans[N];
int next[N], prv[N], con[N];
int a[N];
int n, q, t;
vector < pi > event[N];
void push (int v, int l, int r){
if (l != r){
lz[v + v] += lz[v];
lz[v + v + 1] += lz[v];
}
v3[v] -= s[3][v] * lz[v];
lz[v] = 0;
}
void del (int v, int l, int r, int pos, int type){
push(v, l, r);
if (l == r){
s[type][v] = 0;
if (type == 3)
v3[v] = 0;
}
else {
int mid = (l + r) >> 1;
if (pos <= mid)
del(v + v, l, mid, pos, type);
else
del(v + v + 1, mid + 1, r, pos, type);
s[type][v] = s[type][v + v] + s[type][v + v + 1];
v3[v] = v3[v + v] + v3[v + v + 1];
}
}
void add (int v, int l, int r, int pos, int type){
push(v, l, r);
if (l == r){
if (type == 3){
s[3][v] = a[l];
v3[v] = max(s[1][v], s[2][v]);
if (!v3[v])
v3[v] = s[0][v] * t;
}
else
s[type][v] = 1LL * a[pos] * t;
}
else {
int mid = (l + r) >> 1;
if (pos <= mid)
add(v + v, l, mid, pos, type);
else
add(v + v + 1, mid + 1, r, pos, type);
s[type][v] = s[type][v + v] + s[type][v + v + 1];
v3[v] = v3[v + v] + v3[v + v + 1];
}
}
int srch (int v, int l, int r, int type){
if (l == r)
return l;
else {
int mid = (l + r) >> 1;
if (s[type][v + v])
return srch(v + v, l, mid, type);
return srch(v + v + 1, mid + 1, r, type);
}
}
pi srch2 (int v, int l, int r){
if (l == r){
if (s[1][v])
return {l, 1};
else
return {l, 3};
}
int mid = (l + r) >> 1;
if (max(s[1][v + v + 1], s[3][v + v + 1]))
return srch2(v + v + 1, mid + 1, r);
return srch2(v + v, l, mid);
}
int get_02 (int v, int l, int r, int ql, int qr, int type){
if (ql <= l && r <= qr){
if (s[type][v])
return srch(v, l, r, type);
return n + 1;
}
if (r < ql || qr < l)
return n + 1;
int mid = (l + r) >> 1;
return min(get_02(v + v, l, mid, ql, qr, type), get_02(v + v + 1, mid + 1, r, ql, qr, type));
}
pi get_13 (int v, int l, int r, int ql, int qr){
push(v, l, r);
if (ql <= l && r <= qr){
if (max(s[1][v], s[3][v]))
return srch2(v, l, r);
return {0, 0};
}
if (r < ql || qr < l)
return {0, 0};
int mid = (l + r) >> 1;
return max(get_13(v + v, l, mid, ql, qr), get_13(v + v + 1, mid + 1, r, ql, qr));
}
void build (int v, int l, int r){
if (l == r)
s[0][v] = a[l];
else {
int mid = (l + r) >> 1;
build(v + v, l, mid);
build(v + v + 1, mid + 1, r);
s[0][v] = s[0][v + v] + s[0][v + v + 1];
}
}
ll get (int v, int l, int r, int ql, int qr){
push(v, l, r);
if (ql <= l && r <= qr)
return s[0][v] * (t + 1) + s[1][v] + s[2][v] + v3[v];
if (r < ql || qr < l)
return 0LL;
int mid = (l + r) >> 1;
return get(v + v, l, mid, ql, qr) + get(v + v + 1, mid + 1, r, ql, qr);
}
main(){
cin >> n >> q;
stack < int > st;
for (int i = 1; i <= n; i++){
scanf("%d", &a[i]);
while (!st.empty() && a[st.top()] <= a[i]){
next[st.top()] = i;
st.pop();
}
if (!st.empty())
prv[i] = st.top();
st.push(i);
}
for (int i = 1; i <= n; i++){
if (!next[i])
next[i] = n + 1;
if (!prv[i])
prv[i] = i - N + 4;
if (next[i] - i < i - prv[i]){
event[next[i] - i].pb(mk(1, i));
event[i - prv[i]].pb(mk(3, i));
}
else if (next[i] - i > i - prv[i]){
event[i - prv[i]].pb(mk(2, i));
event[next[i] - i].pb(mk(3, i));
}
else
event[i - prv[i]].pb(mk(3, i));
if (prv[i] != i - N + 4)
event[next[i] - prv[i] - 1].pb(mk(4, i));
}
for (int i = 1; i <= q; i++){
scanf("%d%d%d", &qr[i].fr.fr, &qr[i].sc.fr, &qr[i].sc.sc);
qr[i].fr.sc = i;
}
sort(qr + 1, qr + q + 1);
int i = 1;
build(1, 0, n);
for (t = 1; t <= n; t++){
for (pi it : event[t]){
if (it.fr != 4)
add(1, 0, n, it.sc, it.fr);
del(1, 0, n, it.sc, con[it.sc]);
con[it.sc] = it.fr;
}
lz[1]++;
ll s1, s2;
pi temp;
while (qr[i].fr.fr == t){
temp.fr = get_02(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1, 0);
if (temp.fr == n + 1){
temp.fr = get_02(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1, 2);
if (temp.fr == n + 1){
temp = get_13(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1);
s1 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (next[temp.fr] - qr[i].sc.fr);
}
else
s1 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (temp.fr + t - qr[i].sc.fr + 1);
}
else
s1 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (temp.fr + t - qr[i].sc.fr + 1);
swap(qr[i].sc.fr, qr[i].sc.sc);
qr[i].sc.fr++;
temp.fr = get_02(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1, 0);
if (temp.fr == n + 1){
temp.fr = get_02(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1, 2);
if (temp.fr == n + 1){
temp = get_13(1, 0, n, max(0, qr[i].sc.fr - t - 1), qr[i].sc.fr - 1);
s2 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (next[temp.fr] - qr[i].sc.fr);
}
else
s2 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (temp.fr + t - qr[i].sc.fr + 1);
}
else
s2 = get(1, 0, n, 0, temp.fr) - 1LL * a[temp.fr] * (temp.fr + t - qr[i].sc.fr + 1);
if (qr[i].sc.sc == 1)
s1 = 0;
ans[qr[i].fr.sc] = s2 - s1;
i++;
}
}
for (int i = 1; i <= q; i++)
printf("%lld\n", ans[i]);
}
Compilation message
ho_t5.cpp:151:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
151 | main(){
| ^
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
155 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:183:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
183 | scanf("%d%d%d", &qr[i].fr.fr, &qr[i].sc.fr, &qr[i].sc.sc);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Execution timed out |
1090 ms |
47484 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Execution timed out |
1032 ms |
49948 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1055 ms |
41452 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
