#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Op {
int limit;
int k;
int id;
};
bool operator < (Op a, Op b) {
return a.k < b.k;
}
vector<pair<ll, int>> treemxa;
vector<ll> a;
void buildtreemxa(int v, int tl, int tr) {
if (tl == tr) {
treemxa[v] = {a[tl], tl};
} else {
int tm = (tl + tr) / 2;
buildtreemxa(2 * v, tl, tm);
buildtreemxa(2 * v + 1, tm + 1, tr);
treemxa[v] = max(treemxa[2 * v], treemxa[2 * v + 1]);
}
}
pair<ll, int> getmxa(int v, int tl, int tr, int l, int r) {
if (tr < l || r < tl) {
return {-1LL, 0};
}
if (l <= tl && tr <= r) {
return treemxa[v];
}
int tm = (tl + tr) / 2;
return max(getmxa(2 * v, tl, tm, l, r), getmxa(2 * v + 1, tm + 1, tr, l, r));
}
int n;
vector<pair<ll, ll>> aib1d;
pair<ll, ll> get1d(int x) {
x++;
pair<ll, ll> sol = {0, 0};
while (x) {
sol.first += aib1d[x].first;
sol.second += aib1d[x].second;
x -= x & (-x);
}
return sol;
}
void add1d(int x, pair<ll, ll> v) {
x++;
while (x <= n) {
aib1d[x].first += v.first;
aib1d[x].second += v.second;
x += x & (-x);
}
}
vector<vector<int>> pts;
vector<vector<pair<ll, ll>>> aib;
void add(int x, int y, pair<ll, ll> v) {
x++, y++;
while (x <= n) {
int p = lower_bound(pts[x].begin(), pts[x].end(), y) - pts[x].begin();
p++;
for (int j = p; j <= (int) pts[x].size(); j += j & (-j)) {
aib[x][j].first += v.first;
aib[x][j].second += v.second;
}
x += x & (-x);
}
}
pair<ll, ll> get(int x, int y) {
x++, y++;
pair<ll, ll> s = {0, 0};
while (x >= 1) {
int clw = 0, low = 0, high = (int) pts[x].size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (y <= pts[x][mid]) {
clw = mid + 1;
low = mid + 1;
} else {
high = mid - 1;
}
}
for (int j = clw; j; j -= j & (-j)) {
s.first += aib[x][j].first;
s.second += aib[x][j].second;
}
x -= x & (-x);
}
return s;
}
int main() {
#ifndef ONPC
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
int q;
cin >> n >> q;
a.resize(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
aib1d.resize(n + 1);
aib.resize(n + 1);
pts.resize(n + 1);
treemxa.resize(4 * (n + 7));
buildtreemxa(1, 0, n - 1);
// l, r, t
vector<ll> prn(2 * q, 0);
vector<Op> ops;
for (int i = 0; i < q; i++) {
int l, r, t;
cin >> t >> l >> r;
l--, r--;
ops.push_back({l - 1, t, i});
ops.push_back({r, t, i + q});
}
// next bigger
const int INF = (int) 1e9 + 7;
vector<int> s(n, INF), f(n, -INF);
{
vector<int> stk;
for (int i = n - 1; i >= 0; i--) {
while (!stk.empty() && a[stk.back()] < a[i]) {
stk.pop_back();
}
if (!stk.empty()) {
s[i] = stk.back() - 1;
}
stk.push_back(i);
}
}
{
vector<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[stk.back()] <= a[i]) {
stk.pop_back();
}
if (!stk.empty()) {
f[i] = stk.back() + 1;
}
stk.push_back(i);
}
}
for (int i = 0; i < n; i++) {
if (f[i] != -INF) {
int x = i + 1;
int y = f[i] + 1;
while (x <= n) {
pts[x].push_back(y);
x += x & (-x);
}
}
}
for (int i = 1; i <= n; i++) {
sort(pts[i].begin(), pts[i].end());
pts[i].resize(unique(pts[i].begin(), pts[i].end()) - pts[i].begin());
aib[i].resize((int) pts[i].size() + 1, make_pair(0, 0));
}
sort(ops.begin(), ops.end());
ll h = 0;
vector<int> c1(n, 1), c2(n, 1);
vector<int> indsfi(n); iota(indsfi.begin(), indsfi.end(), 0);
vector<int> indssi(n); iota(indssi.begin(), indssi.end(), 0);
vector<int> indsfisi(n); iota(indsfisi.begin(), indsfisi.end(), 0);
sort(indsfi.begin(), indsfi.end(), [&] (int i, int j) {
return i - f[i] > j - f[j];
});
sort(indssi.begin(), indssi.end(), [&] (int i, int j) {
return s[i] - i > s[j] - j;
});
sort(indsfisi.begin(), indsfisi.end(), [&] (int i, int j) {
return s[i] - f[i] > s[j] - f[j];
});
vector<ll> foo(n, 0), bar(n, 0);
for (int i = 0; i < n; i++) {
foo[i] += a[i];
bar[i] += a[i];
if (f[i] == -INF) {
add1d(i, {a[i], a[i]});
} else {
add(i, f[i], {a[i], a[i]});
}
}
for (auto &it : ops) {
int limit = it.limit;
if (limit < 0) {
continue;
}
int k = it.k;
int id = it.id;
while (!indsfi.empty()) {
int i = indsfi.back();
if (i - f[i] <= k) {
indsfi.pop_back();
c1[i]--;
foo[i] += a[i] * (i - f[i]);
bar[i] -= a[i];
if (f[i] == -INF) {
add1d(i, {a[i] * (i - f[i]), a[i]});
} else {
add(i, f[i], {a[i] * (i - f[i]), a[i]});
}
} else {
break;
}
}
while (!indssi.empty()) {
int i = indssi.back();
if (s[i] - i <= k) {
indssi.pop_back();
c2[i]--;
foo[i] += a[i] * (s[i] - i);
bar[i] -= a[i];
if (f[i] == -INF) {
add1d(i, {a[i] * (s[i] - i), -a[i]});
} else {
add(i, f[i], {a[i] * (s[i] - i), -a[i]});
}
} else {
break;
}
}
while (!indsfisi.empty()) {
int i = indsfisi.back();
if (f[i] > s[i] - k) {
indsfisi.pop_back();
foo[i] = bar[i] = 0;
if (f[i] == -INF) {
add1d(i, {-foo[i], -bar[i]});
} else {
add(i, f[i], {-foo[i], -bar[i]});
}
} else {
break;
}
}
ll sol = 0;
{
int i = getmxa(1, 0, n - 1, max(0, limit - k), limit).second;
sol += 1LL * a[i] * (limit - min(s[i], i + k));
}
pair<ll, ll> s = get1d(limit);
sol += s.first + s.second * k;
for (int i = 0; i < n; i++) {
if (0 <= f[i] && f[i] <= limit - k && i <= limit) {
sol += (foo[i] + bar[i] * k);
}
}
prn[id] = sol;
}
for (int i = 0; i < q; i++) {
cout << prn[i + q] - prn[i] << "\n";
}
return 0;
}
Compilation message
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:173:5: warning: unused variable 'h' [-Wunused-variable]
173 | ll h = 0;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
272 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Execution timed out |
1088 ms |
76072 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Execution timed out |
1100 ms |
75836 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1095 ms |
62624 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
272 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Execution timed out |
1088 ms |
76072 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |