oj.uz

Submission #1012892

# Submission time Handle Problem Language Result Execution time Memory
1012892 2024-07-02T19:45:44 Z EJIC_B_KEDAX Fire (JOI20_ho_t5) C++17
6 / 100
 242 ms 66512 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]);
            assert(nxt[i] - prv[i] <= n);
        }
    }
    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 0 ms 344 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 0 ms 344 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 0 ms 344 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 174 ms 64900 KB Output is correct
2 Correct 214 ms 64676 KB Output is correct
3 Correct 187 ms 66096 KB Output is correct
4 Correct 205 ms 64476 KB Output is correct
5 Correct 193 ms 64384 KB Output is correct
6 Correct 191 ms 64936 KB Output is correct
7 Correct 202 ms 66512 KB Output is correct
8 Correct 233 ms 65364 KB Output is correct
9 Correct 208 ms 65152 KB Output is correct
10 Correct 242 ms 65476 KB Output is correct
11 Correct 192 ms 64888 KB Output is correct
12 Correct 204 ms 65132 KB Output is correct
13 Correct 174 ms 64948 KB Output is correct
14 Correct 198 ms 64880 KB Output is correct

Subtask #5
0 / 80.0

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