| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1012895 |
2024-07-02T19:47:28 Z |
EJIC_B_KEDAX |
Fire (JOI20_ho_t5) |
C++17 |
|
218 ms |
66420 KB |
#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937 mt(123);
void solve();
void init();
int32_t main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cout << fixed << setprecision(30);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
struct segment_tree {
vector<ll> st;
int sz;
segment_tree() = default;
segment_tree(vector<int> a) {
sz = 1;
while (sz < a.size()) {
sz <<= 1;
}
st.resize(2 * sz, 0);
for (int i = 0; i < a.size(); i++) {
st[sz + i] = a[i];
}
for (int i = sz - 1; i > 0; i--) {
st[i] = st[2 * i] + st[2 * i + 1];
}
}
void add(int i, ll x) {
i += sz;
while (i) {
st[i] += x;
i >>= 1;
}
}
ll get(int l, int r) {
l += sz;
r += sz;
ll res = 0;
while (l <= r) {
if (l & 1) {
res += st[l++];
}
if (~r & 1) {
res += st[r--];
}
l >>= 1;
r >>= 1;
}
return res;
}
};
struct mseg_tree {
segment_tree def, step;
int now_step;
mseg_tree() = default;
mseg_tree(int n) {
now_step = 0;
def = segment_tree(vector<int>(n, 0));
step = segment_tree(vector<int>(n, 0));
}
void add_def(int i, int x) {
def.add(i, x);
}
void add_step(int i, int x) {
step.add(i, x);
def.add(i, -1ll * x * now_step);
}
void next_step() {
now_step++;
}
void set_step(int new_step) {
now_step = new_step;
}
ll get(int l, int r) {
return def.get(l, r) + now_step * step.get(l, r);
}
};
struct sparse_max {
using Type = pair<int, int>;
vector<vector<Type>> sp;
vector<int> p;
sparse_max(const vector<Type>& a) {
int n = a.size(), lg = 0;
while ((1 << lg) < n) {
lg++;
}
sp.resize(lg, vector<Type>(n));
for (int i = 0; i < n; i++) {
sp[0][i] = a[i];
}
for (int l = 1; l < lg; l++) {
for (int i = 0; i <= n - (1 << l); i++) {
sp[l][i] = max(sp[l - 1][i], sp[l - 1][i + (1 << (l - 1))]);
}
}
int nw = 0;
p.resize(n + 1, 0);
for (int i = 1; i <= n; i++) {
if ((1 << nw) * 2 < i) {
nw++;
}
p[i] = nw;
}
}
Type get(int l, int r) {
int lev = p[r - l + 1];
return max(sp[lev][l], sp[lev][r - (1 << lev) + 1]);
}
};
struct sparse_min {
using Type = pair<int, int>;
vector<vector<Type>> sp;
vector<int> p;
sparse_min(const vector<Type>& a) {
int n = a.size(), lg = 0;
while ((1 << lg) < n) {
lg++;
}
sp.resize(lg, vector<Type>(n));
for (int i = 0; i < n; i++) {
sp[0][i] = a[i];
}
for (int l = 1; l < lg; l++) {
for (int i = 0; i <= n - (1 << l); i++) {
sp[l][i] = min(sp[l - 1][i], sp[l - 1][i + (1 << (l - 1))]);
}
}
int nw = 0;
p.resize(n + 1, 0);
for (int i = 1; i <= n; i++) {
if ((1 << nw) * 2 < i) {
nw++;
}
p[i] = nw;
}
}
Type get(int l, int r) {
int lev = p[r - l + 1];
return min(sp[lev][l], sp[lev][r - (1 << lev) + 1]);
}
};
void init() {}
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n), nxt(n), prv(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
mseg_tree st(n);
for (int i = 0; i < n; i++) {
st.add_step(i, a[i]);
}
vector<pair<int, int>> stack(1, {INT32_MAX / 2, n});
for (int i = n - 1; i >= 0; i--) {
while (a[i] >= stack.back().x) {
stack.pop_back();
}
nxt[i] = stack.back().y;
stack.emplace_back(a[i], i);
}
stack.clear(); stack.emplace_back(INT32_MAX, -1);
for (int i = 0; i < n; i++) {
while (a[i] > stack.back().x) {
stack.pop_back();
}
prv[i] = stack.back().y;
stack.emplace_back(a[i], i);
}
vector<pair<int, int>> fsp(n);
for (int i = 0; i < n; i++) {
fsp[i] = {a[i], -i};
}
sparse_max sp(fsp);
vector<vector<pair<int, int>>> ev(n + 1);
vector<vector<int>> qu(n + 1);
vector<pair<int, int>> seg(q);
vector<ll> ans(q);
for (int i = 0; i < q; i++) {
int t, l, r;
cin >> t >> l >> r; l--; r--;
qu[t].push_back(i);
seg[i] = {l, r};
}
for (int i = 0; i < n; i++) {
ev[nxt[i] - i].emplace_back(i, -a[i]);
assert(nxt[i] - i <= n && nxt[i] - i >= 0);
if (prv[i] != -1) {
ev[i - prv[i]].emplace_back(i, -a[i]);
ev[nxt[i] - prv[i]].emplace_back(i, a[i]);
}
}
for (int t = 0; t <= n; t++) {
for (auto [i, v] : ev[t]) {
st.add_step(i, v);
}
st.next_step();
for (int i : qu[t]) {
auto [l, r] = seg[i];
r++;
ll lans = 0, rans = 0;
{
auto [mx, mxi] = sp.get(max(0, l - t), l);
mxi *= -1;
lans = st.get(mxi + 1, n - 1);
int lst = min({mxi + t, nxt[mxi] - 1});
lans += 1ll * (lst - l + 1) * mx;
}
if (r < n) {
auto [mx, mxi] = sp.get(max(0, r - t), r);
mxi *= -1;
rans = st.get(mxi + 1, n - 1);
int lst = min(mxi + t, nxt[mxi] - 1);
rans += 1ll * (lst - r + 1) * mx;
}
ans[i] = lans - rans;
}
}
for (ll i : ans) {
cout << i << '\n';
}
}
Compilation message
ho_t5.cpp: In constructor 'segment_tree::segment_tree(std::vector<int>)':
ho_t5.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | while (sz < a.size()) {
| ~~~^~~~~~~~~~
ho_t5.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
196 ms |
64896 KB |
Output is correct |
| 2 |
Correct |
190 ms |
64716 KB |
Output is correct |
| 3 |
Correct |
195 ms |
66096 KB |
Output is correct |
| 4 |
Correct |
190 ms |
64604 KB |
Output is correct |
| 5 |
Correct |
193 ms |
64472 KB |
Output is correct |
| 6 |
Correct |
200 ms |
65008 KB |
Output is correct |
| 7 |
Correct |
191 ms |
66420 KB |
Output is correct |
| 8 |
Correct |
213 ms |
65244 KB |
Output is correct |
| 9 |
Correct |
218 ms |
64980 KB |
Output is correct |
| 10 |
Correct |
184 ms |
65360 KB |
Output is correct |
| 11 |
Correct |
201 ms |
64892 KB |
Output is correct |
| 12 |
Correct |
194 ms |
65136 KB |
Output is correct |
| 13 |
Correct |
182 ms |
64888 KB |
Output is correct |
| 14 |
Correct |
188 ms |
64876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
