Submission #1014385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014385		EJIC_B_KEDAX	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	715 ms	118020 KiB

Main

#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 = 1;
        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 segment_tree2 {
    vector<ll> st1, st2, lazy;
    int sz;
    segment_tree2(const vector<int>& a) {
        sz = 1;
        while (sz < a.size()) {
            sz <<= 1;
        }
        st1.resize(2 * sz);
        st2.resize(2 * sz);
        lazy.resize(2 * sz);
        for (int i = 0; i < 2 * sz; i++) {
            st1[i] = 0;
            st2[i] = 0;
            lazy[i] = 0;
        }
        for (int i = 0; i < a.size(); i++) {
            st1[sz + i] = a[i];
        }
        for (int i = sz - 1; i > 0; i--) {
            st1[i] = st1[2 * i] + st1[2 * i + 1];
        }
    }
    void push(int i) {
        if (i < sz && lazy[i]) {
            st2[2 * i] = st1[2 * i] * lazy[i];
            st2[2 * i + 1] = st1[2 * i + 1] * lazy[i];
            lazy[2 * i] = lazy[i];
            lazy[2 * i + 1] = lazy[i];
            lazy[i] = 0;
        }
    }
    void set(int l, int r, int v, int l1 = 0, int r1 = -1, int i = 1) {
        if (r1 == -1) {
            r1 += sz;
        }
        if (l1 >= l && r1 <= r) {
            lazy[i] = v;
            st2[i] = st1[i] * v;
            return;
        }
        if (l1 > r || r1 < l) {
            return;
        }
        push(i);
        set(l, r, v, l1, (l1 + r1) / 2, 2 * i);
        set(l, r, v, (l1 + r1) / 2 + 1, r1, 2 * i + 1);
        st2[i] = st2[2 * i] + st2[2 * i + 1];
    }

    ll get(int l, int r, int l1 = 0, int r1 = -1, int i = 1) {
        if (r1 == -1) {
            r1 += sz;
        }
        if (l1 >= l && r1 <= r) {
            return st2[i];
        }
        if (l1 > r || r1 < l) {
            return 0;
        }
        push(i);
        return get(l, r, l1, (l1 + r1) / 2, 2 * i) + get(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 1);
    }
};

void init() {}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n), w(n), nxt(n), prv(n), start_time(q);
    vector<ll> pref(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i]; a[i] *= -1;
    }
    pref[0] = 0;
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + w[i];
    }
    mseg_tree st(n);
    for (int i = 0; i < n; i++) {
        st.add_step(i, a[i]);
    }
    vector<pair<int, int>> fsp(n), fsp2(n);
    for (int i = 0; i < n; i++) {
        fsp[i] = {a[i], -i};
        fsp2[i] = {w[i], 0};
    }
    sparse_max sp(fsp), spw(fsp2);
    vector<pair<ll, pair<int, int>>> ev;
    vector<pair<ll, int>> qu;
    vector<pair<int, int>> seg(q);
    vector<ll> ans(q);
    vector<vector<int>> start(n);
    for (int i = 0; i < q; i++) {
        int t, l, r;
        cin >> l >> r >> t; l--; r--; t--;
        qu.emplace_back(t, i);
        seg[i] = {l, r};
        start_time[i] = t;
        start[l].push_back(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);
    }
    for (int i = 0; i < n; i++) {
        ev.emplace_back(pref[nxt[i]] - pref[i], make_pair(i, -a[i]));
        if (prv[i] != -1) {
            ev.emplace_back(pref[i] - pref[prv[i]], make_pair(i, -a[i]));
            ev.emplace_back(pref[nxt[i]] - pref[prv[i]], make_pair(i, a[i]));
        }
    }
    sort(all(ev));
    sort(all(qu));
    int ptrev = 0, ptrqu = 0, t = 0;
    while (ptrqu < qu.size()) {
        while (ptrev < ev.size() && ev[ptrev].x == t) {
            st.add_step(ev[ptrev].y.x, ev[ptrev].y.y);
            ptrev++;
        }
        st.next_step();
        while (ptrqu < qu.size() && qu[ptrqu].x == t) {
            int i = qu[ptrqu++].y;
            auto [l, r] = seg[i];
            ll lans = 0, rans = 0;
            if (pref[l] + t < pref[r]) {
                {
                    int left = l, right = n;
                    while (right - left > 1) {
                        int mid = (right + left) / 2;
                        if (pref[mid] - pref[l] > t) {
                            right = mid;
                        } else {
                            left = mid;
                        }
                    }
                    auto [mx, mxi] = sp.get(l, left);
                    mxi *= -1;
                    lans = st.get(mxi + 1, n - 1);
                    ll lst = min(pref[mxi] + t, pref[nxt[mxi]] - 1);
                    lans += 1ll * (lst - pref[l] - t + 1) * mx;
                }
                if (r < n) {
                    int left = -1, right = r;
                    while (right - left > 1) {
                        int mid = (right + left) / 2;
                        if (pref[r] - pref[mid] > t) {
                            left = mid;
                        } else {
                            right = mid;
                        }
                    }
                    auto [mx, mxi] = sp.get(right, r);
                    mxi *= -1;
                    rans = st.get(mxi + 1, n - 1);
                    ll lst = min(pref[mxi] + t, pref[nxt[mxi]] - 1);
                    rans += 1ll * (lst - pref[r] + 1) * mx;
                }
            }
            ans[i] = lans - rans;
        }
        t++;
    }
    segment_tree2 st2(w);
    for (int pos = n - 1; pos >= 0; pos--) {
        st2.set(pos, nxt[pos] - 1, a[pos]);
        for (int i : start[pos]) {
            auto [l, r] = seg[i];
            int t = min(1ll * start_time[i], pref[r] - pref[l]);
            int left = l, right = n;
            while (right - left > 1) {
                int mid = (right + left) / 2;
                if (pref[mid] - pref[l] > t) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            ll weight = st2.get(left, left) / w[left];
            ans[i] += st2.get(l, left - 1) + weight * (pref[l] + t - pref[left]);
        }
    }
    for (int i = 0; i < q; i++) {
        if (spw.get(seg[i].x, seg[i].y - 1).x <= start_time[i] + 1) {
            cout << -ans[i] << '\n';
        } else {
            cout << "-1\n";
        }
    }
}

Compilation message (stderr)

Main.cpp: In constructor 'segment_tree::segment_tree(std::vector<int>)':
Main.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()) {
      |                ~~~^~~~~~~~~~
Main.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++) {
      |                         ~~^~~~~~~~~~
Main.cpp: In constructor 'segment_tree2::segment_tree2(const std::vector<int>&)':
Main.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         while (sz < a.size()) {
      |                ~~~^~~~~~~~~~
Main.cpp:149:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:264:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  264 |     while (ptrqu < qu.size()) {
      |            ~~~~~~^~~~~~~~~~~
Main.cpp:265:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  265 |         while (ptrev < ev.size() && ev[ptrev].x == t) {
      |                ~~~~~~^~~~~~~~~~~
Main.cpp:270:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  270 |         while (ptrqu < qu.size() && qu[ptrqu].x == t) {
      |                ~~~~~~^~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44