#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 2e5 + 7;
int n, q, a[N], l[N], r[N];
vector <int> d[N];
vector <ii> mem[N], meml[N];
void add(int l, int r, int i, int x) {
mem[l].app(mp(i, x));
mem[r + 1].app(mp(i, -x));
}
void addl(int l, int r, int i, int x) {
meml[l].app(mp(i, x));
meml[r + 1].app(mp(i, -x));
}
int link_l[N], link_r[N];
int ans[N];
struct Fen {
int f[N];
void clear() {
for (int i = 0; i < N; ++i) f[i] = 0;
}
void add(int i, int x) {
for (; i < N; i |= i + 1)
f[i] += x;
}
int get(int i) {
int ans = 0;
for (; i >= 0; i &= i + 1, --i) ans += f[i];
return ans;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
} f, fl;
int pref_mx[N], pref_sum[N];
//bigger left, not less right
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
#define endl '\n'
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
cin >> n >> q;
for (int i = 0; i < n; ++i) {
cin >> a[i];
pref_mx[i + 1] = max(pref_mx[i], a[i]);
pref_sum[i + 1] = pref_sum[i] + pref_mx[i + 1];
}
for (int i = 0; i < q; ++i) {
int t;
cin >> t >> l[i] >> r[i];
--l[i]; --r[i];
d[t + 1].app(i);
}
vector <int> s;
for (int i = 0; i < n; ++i) {
while (s.size() && a[s.back()] <= a[i]) {
link_r[s.back()] = i;
s.pop_back();
}
s.app(i);
}
for (int e : s)
link_r[e] = n;
s.clear();
for (int i = n - 1; i >= 0; --i) {
while (s.size() && a[s.back()] < a[i]) {
link_l[s.back()] = i;
s.pop_back();
}
s.app(i);
}
for (int e : s)
link_l[e] = -1;
s.clear();
for (int i = 0; i < n; ++i) {
if (link_r[i] - i < i - link_l[i]) {
for (int j = i; j < link_r[i]; ++j) {
int len1 = j - i + 1;
int len2 = j - link_l[i];
if (link_l[i] == -1)
len2 = N - 2;
add(len1, len2, j, a[i]);
}
}
else {
for (int j = link_l[i] + 1; j <= i; ++j) {
int len1 = i - j + 1;
int len2 = link_r[i] - j;
if (link_r[i] == n)
len2 = N - 2;
addl(len1, len2, j, a[i]);
//cout << "addl " << len1 << ' ' << len2 << ' ' << j << ' ' << a[i] << endl;
}
}
}
f.clear();
fl.clear();
for (int len = 1; len < N; ++len) {
for (auto e : mem[len])
f.add(e.f, e.s);
for (auto e : meml[len]) {
fl.add(e.f, e.s);
//cout << "addf " << len << ' ' << e.f << ' ' << e.s << endl;
}
for (auto e : d[len]) {
ans[e] += f.get(l[e], r[e]);
for (int i = l[e]; i <= r[e]; ++i)
if (i < len)
ans[e] += pref_mx[i + 1];
else
ans[e] += fl.get(i - len + 1, i - len + 1);
/*
if (l[e] + 1 < len) {
int t = min(len, r[e] + 1);
ans[e] += pref_sum[t] - pref_sum[l[e]];
l[e] = t;
}
if (l[e] <= r[e])
ans[e] += fl.get(l[e] - len + 1, r[e] - len + 1);
*/
}
}
for (int i = 0; i < q; ++i)
cout << ans[i] << '\n';
#ifdef HOME
cout << Time << endl;
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
17656 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
17656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
17656 KB |
Output is correct |
| 2 |
Execution timed out |
1102 ms |
80104 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
17656 KB |
Output is correct |
| 2 |
Incorrect |
375 ms |
84684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1096 ms |
44804 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
17656 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
17656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
