Submission #957401

#	Time	Username	Problem	Language	Result	Execution time	Memory
957401		peterandvoi	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	463 ms	60372 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long

const int N = (int) 2e5 + 5;

int n, m;
int a[N], b[N], x[N], r[N], s[N], t[N], u[N], res[N];
vector<int> g[N], Q[N];

namespace st {
    int tree[4 * N];
    int idx[4 * N];

    int cmp(int i, int j) {
        return b[i] < b[j] ? i : j;
    }

    void bld(int id = 1, int l = 1, int r = n) {
        if (l == r) {
            tree[id] = a[l];
            idx[id] = l;
        } else {
            int mid = l + r >> 1;
            bld(id << 1, l, mid);
            bld(id << 1 | 1, mid + 1, r);
            idx[id] = cmp(idx[id << 1], idx[id << 1 | 1]);
            tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
        }
    }

    int get(int u, int v, int id = 1, int l = 1, int r = n) {
        if (u <= x[l] && x[r] <= v) {
            return idx[id];
        }
        int mid = l + r >> 1;
        if (u <= x[mid] && x[mid] < v) {
            return cmp(get(u, v, id << 1, l, mid), get(u, v, id << 1 | 1, mid + 1, r));
        }
        if (x[mid] < u) {
            return get(u, v, id << 1 | 1, mid + 1, r);
        }
        return get(u, v, id << 1, l, mid);
    }

    int qry(int u, int v, int id = 1, int l = 1, int r = n) {
        if (u <= l && r <= v) {
            return tree[id];
        }
        int mid = l + r >> 1;
        if (u <= mid && mid < v) {
            return max(qry(u, v, id << 1, l, mid), qry(u, v, id << 1 | 1, mid + 1, r));
        }
        if (mid < u) {
            return qry(u, v, id << 1 | 1, mid + 1, r);
        }
        return qry(u, v, id << 1, l, mid);
    }
}

struct fenwick {
    int n;
    vector<int> s;

    fenwick() {};

    fenwick(int n): n(n) {
        s.resize(n);
    }

    void upd(int i, int x) {
        for (; i <= n; i += i & -i) {
            s[i - 1] += x;
        }
    }

    int get(int i) {
        int res = 0;
        for (; i; i -= i & -i) {
            res += s[i - 1];
        }
        return res;
    }

    void upd(int l, int r, int x) {
        upd(l, x);
        upd(r + 1, -x);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        x[i + 1] = x[i] + a[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }
    st::bld();
    vector<int> values;
    for (int i = 1; i <= m; ++i) {
        cin >> s[i] >> t[i] >> u[i];
        if (st::qry(s[i], t[i] - 1) > u[i]) {
            res[i] = -1;
        } else {
            values.emplace_back(u[i]);
            int r = st::get(max(x[s[i]], x[t[i]] - u[i]), min(x[n], x[t[i]]));
            res[i] = b[r] * (x[t[i]] - x[r]);
            Q[s[i]].emplace_back(i);
            Q[r].emplace_back(-i);
        }
    }
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    auto idx = [&](int x) {
        return lower_bound(values.begin(), values.end(), x) - values.begin() + 1;
    };
    int k = (int) values.size();
    fenwick ft1(k), ft2(k);
    auto get = [&](int U) {
        int i = idx(U);
        return ft1.get(i) * U + ft2.get(i);
    };
    vector<int> st;
    for (int i = n; i >= 1; --i) {
        while (st.size() && b[st.back()] >= b[i]) {
            st.pop_back();
        }
        r[i] = st.size() ? st.back() : n + 1;
        st.emplace_back(i);
    }
    while (st.size()) {
        st.pop_back();
    }
    for (int i = 1; i <= n; ++i) {
        while (st.size() && b[st.back()] > b[i]) {
            st.pop_back();
        }
        if (st.size()) {
            g[st.back()].emplace_back(i);
        }
        st.emplace_back(i);
    }
    for (int i = n; i >= 1; --i) {
        int delta = x[r[i]] - x[i];
        int pos = idx(delta);
        if (pos > 1) {
            ft1.upd(1, pos - 1, b[i]);
        }
        if (pos <= k) {
            ft2.upd(pos, k, delta * b[i]);
        }
        for (int j : g[i]) {
            int delta = x[j] - x[i];
            int pos = idx(delta);
            if (pos <= k) {
                ft1.upd(pos, k, -b[j]);
                ft2.upd(pos, k, delta * b[j]);
            }
            delta = x[r[j]] - x[i];
            pos = idx(delta);
            if (pos <= k) {
                ft1.upd(pos, k, b[j]);
                ft2.upd(pos, k, -delta * b[j]);
            }
        }
        for (int id : Q[i]) {
            int sign = id < 0 ? -1 : 1;
            res[sign * id] += sign * get(u[sign * id]);
        }
    }
    for (int i = 1; i <= m; ++i) {
        cout << res[i] << "\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'void st::bld(long long int, long long int, long long int)':
Main.cpp:32:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |             int mid = l + r >> 1;
      |                       ~~^~~
Main.cpp: In function 'long long int st::get(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:44:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'long long int st::qry(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = l + r >> 1;
      |                   ~~^~~

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