oj.uz

답안 #1012901

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1012901 2024-07-02T19:51:03 Z EJIC_B_KEDAX Fire (JOI20_ho_t5) C++17
6 / 100
 226 ms 66360 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];
    }
    assert(a[0] != 9);
    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 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 64976 KB Output is correct
2 Correct 208 ms 64624 KB Output is correct
3 Correct 197 ms 66280 KB Output is correct
4 Correct 195 ms 64412 KB Output is correct
5 Correct 226 ms 64388 KB Output is correct
6 Correct 206 ms 65076 KB Output is correct
7 Correct 177 ms 66360 KB Output is correct
8 Correct 197 ms 65364 KB Output is correct
9 Correct 212 ms 65080 KB Output is correct
10 Correct 196 ms 65584 KB Output is correct
11 Correct 201 ms 64892 KB Output is correct
12 Correct 209 ms 65136 KB Output is correct
13 Correct 194 ms 64884 KB Output is correct
14 Correct 199 ms 64984 KB Output is correct

Subtask #5
0 / 80.0

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