Submission #204037

#TimeUsernameProblemLanguageResultExecution timeMemory
204037savacskaFire (JOI20_ho_t5)C++14
1 / 100
1100 ms20072 KiB
#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], leng[CS + 5][CS + 5]; 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; for (int j = 0; j <= CS; j++) for (int z = 0; z <= CS; z++) leng[j][z] = 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; leng[z - j][z - lef] += (ll) mx; } } for (int j = 0; j <= rig - lef; j++) for (int z = 1; z <= rig - lef; z++) leng[j][z] += leng[j][z - 1]; for (int j = lef; j <= rig; j++) { 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 += leng[tim][j - lef]; } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...