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>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long long ll;
const int CS = 500;
ll summa[200005], pref[200005], answer[200005], smallsum[200005];
int mas[200005], maxim[200005];
vector <pair <int, int> > zapr[200005];
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n, quer;
cin >> n >> quer;
for (int i = 1; i <= n; i++) cin >> mas[i];
for (int i = 1; i <= quer; i++)
{
int tim, lef, rig;
cin >> tim >> lef >> rig;
zapr[rig].pb(mp(tim, i));
zapr[lef - 1].pb(mp(tim, -i));
}
for (int i = 1; i <= (n - 1) / CS + 1; i++)
{
int lef = (i - 1) * CS + 1, rig = min(n, i * CS);
for (int j = 0; j <= n; j++) summa[j] = 0, smallsum[j] = 0;
int uk = lef, tekmax = mas[lef], cur = mas[lef - 1];
for (int j = lef - 1; j >= 1; j--)
{
cur = max(cur, mas[j]);
maxim[j] = cur;
while (uk <= rig && tekmax < cur)
{
uk++;
tekmax = max(tekmax, mas[uk]);
}
summa[lef - j] += (ll) cur, summa[uk - j] -= (ll) cur;
}
for (int j = 0; j >= lef - n; j--)
{
summa[lef - j] += (ll) cur;
summa[min(uk - j, n + 1)] -= (ll) cur;
}
uk = lef - 1, tekmax = mas[lef - 1], cur = mas[lef];
for (int j = lef; j <= rig; j++)
{
cur = max(cur, mas[j]);
maxim[j] = cur;
while (uk > 0 && tekmax <= cur)
{
uk--;
tekmax = max(tekmax, mas[uk]);
}
if (uk == 0) summa[j - uk] += (ll) cur, summa[n + 1] -= (ll) cur;
summa[j - lef + 1] += (ll) cur, summa[j - uk] -= (ll) cur;
}
for (int j = 1; j <= n; j++) summa[j] += summa[j - 1];
for (int j = lef; j <= rig; j++)
{
int mx = mas[j];
for (int z = j; z <= rig; z++)
{
mx = max(mx, mas[z]);
summa[z - j] += (ll) mx;
}
}
for (int j = lef; j <= rig; j++)
{
int mx = mas[j];
for (int z = j; z >= lef; z--)
{
mx = max(mx, mas[z]);
smallsum[j - z] += (ll) mx;
}
for (int z = 0; z < (int) zapr[j].size(); z++)
{
int tim = zapr[j][z].x, num = zapr[j][z].y;
if (num > 0) answer[num] += pref[tim];
else answer[-num] -= pref[tim];
ll ans = 0;
if (tim <= CS)
{
for (int k = lef; k <= min (j, lef + tim - 1); k++) ans += (ll) max(maxim[k], maxim[max(k - tim, 1)]);
if (j - tim >= lef) ans += smallsum[tim];
}
else
{
for (int k = lef; k <= j; k++) ans += (ll) max(maxim[k], maxim[max(k - tim, 1)]);
}
if (num > 0) answer[num] += ans;
else answer[-num] -= ans;
}
}
for (int j = 0; j <= n; j++) pref[j] += summa[j];
}
for (int i = 1; i <= quer; i++) cout << answer[i] << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |