oj.uz

답안 #1012899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1012899 2024-07-02T19:50:03 Z EJIC_B_KEDAX Fire (JOI20_ho_t5) C++17
6 / 100
 214 ms 66520 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, 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 64900 KB Output is correct
2 Correct 214 ms 64816 KB Output is correct
3 Correct 196 ms 66052 KB Output is correct
4 Correct 194 ms 64456 KB Output is correct
5 Correct 208 ms 64384 KB Output is correct
6 Correct 193 ms 64864 KB Output is correct
7 Correct 186 ms 66520 KB Output is correct
8 Correct 192 ms 65396 KB Output is correct
9 Correct 180 ms 65172 KB Output is correct
10 Correct 214 ms 65620 KB Output is correct
11 Correct 200 ms 64728 KB Output is correct
12 Correct 195 ms 65132 KB Output is correct
13 Correct 206 ms 64892 KB Output is correct
14 Correct 186 ms 64876 KB Output is correct

Subtask #5
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -