oj.uz

Submission #1012891

# Submission time Handle Problem Language Result Execution time Memory
1012891 2024-07-02T19:43:31 Z EJIC_B_KEDAX Fire (JOI20_ho_t5) C++17
6 / 100
 225 ms 69784 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]);
        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++) {
      |                         ~~^~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 68740 KB Output is correct
2 Correct 194 ms 67948 KB Output is correct
3 Correct 225 ms 69784 KB Output is correct
4 Correct 211 ms 67996 KB Output is correct
5 Correct 194 ms 68040 KB Output is correct
6 Correct 210 ms 68172 KB Output is correct
7 Correct 197 ms 69624 KB Output is correct
8 Correct 180 ms 68952 KB Output is correct
9 Correct 182 ms 68596 KB Output is correct
10 Correct 220 ms 68688 KB Output is correct
11 Correct 200 ms 68328 KB Output is correct
12 Correct 192 ms 68548 KB Output is correct
13 Correct 213 ms 68468 KB Output is correct
14 Correct 192 ms 68464 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -