| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 204026 |
2020-02-24T00:32:58 Z |
savacska |
Fire (JOI20_ho_t5) |
C++14 |
|
1000 ms |
17400 KB |
#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 = 450;
struct My_queue
{
deque <pair <int, int> > qu;
void add(int x, int pos)
{
while (!qu.empty() && qu.back().x <= x) qu.pop_back();
qu.push_back(mp(x, pos));
return;
}
int get_max()
{
return qu[0].x;
}
void pop(int pos)
{
if (qu[0].y == pos) qu.pop_front();
return;
}
};
ll summa[200005], pref[200005], answer[200005];
int mas[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;
int uk = lef, tekmax = mas[lef], cur = mas[lef - 1];
for (int j = lef - 1; j >= 1; j--)
{
cur = max(cur, mas[j]);
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]);
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++)
{
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];
My_queue S;
ll ans = 0;
for (int k = max(lef - tim, 1); k < lef; k++) S.add(mas[k], k);
for (int k = lef; k <= j; k++)
{
S.add(mas[k], k);
ans += (ll) S.get_max();
S.pop(k - tim);
}
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 |
| 1 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 7 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 8 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 9 |
Correct |
8 ms |
5116 KB |
Output is correct |
| 10 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 11 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 12 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 13 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 14 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 15 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 16 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 17 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 18 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 19 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 20 |
Correct |
9 ms |
5116 KB |
Output is correct |
| 21 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 22 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 23 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 24 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 25 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 26 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 27 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 28 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 29 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 30 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 31 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 32 |
Correct |
8 ms |
5112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 2 |
Execution timed out |
1096 ms |
16992 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 2 |
Execution timed out |
1095 ms |
17400 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1097 ms |
16888 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 4 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 7 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 8 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 9 |
Correct |
8 ms |
5116 KB |
Output is correct |
| 10 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 11 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 12 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 13 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 14 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 15 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 16 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 17 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 18 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 19 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 20 |
Correct |
9 ms |
5116 KB |
Output is correct |
| 21 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 22 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 23 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 24 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 25 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 26 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 27 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 28 |
Correct |
9 ms |
5112 KB |
Output is correct |
| 29 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 30 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 31 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 32 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 33 |
Execution timed out |
1089 ms |
17272 KB |
Time limit exceeded |
| 34 |
Halted |
0 ms |
0 KB |
- |
