Submission #381161

#	Time	Username	Problem	Language	Result	Execution time	Memory
381161		usachevd0	Dungeon 3 (JOI21_ho_t5)	C++14	100 / 100	1059 ms	146648 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) { for (auto x : v) stream << x << ' '; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; }

#define int ll

const int INF32 = 1e9;
const int N = 200005;
int n, Q;
ll X[N];
int D[N];
ll B[N];
int leftLeq[N], rightLe[N];

struct Query
{
    int s, t, idx;
    ll u;
    int sgn;
} qr[N];
ll ans[N];

namespace rmaxq
{
    const int logN = 18;
    const int NN = 1 << logN;
    int mx[2 * NN];
    void build(int *a, int n)
    {
        for (int i = 0; i < n; ++i)
            mx[i + NN] = a[i];
        for (int v = NN - 1; v >= 1; --v)
            mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    }
    int gt(int l, int r)
    {
        int ans = 0;
        for (l += NN, r += NN; l <= r; l >>= 1, r >>= 1)
        {
            if (l & 1)  chkmax(ans, mx[l++]);
            if (~r & 1) chkmax(ans, mx[r--]);
        }
        return ans;
    }
}

namespace rminq
{
    const int logN = 18;
    const int NN = 1 << logN;
    int mn[2 * NN];
    void build(int n)
    {
        memset(mn, 0, sizeof mn);
        for (int i = 0; i < n; ++i)
            mn[i + NN] = i;
        for (int v = NN - 1; v >= 1; --v)
            if (B[mn[v << 1]] <= B[mn[v << 1 | 1]])
                mn[v] = mn[v << 1];
            else
                mn[v] = mn[v << 1 | 1];
    }
    int gt(int l, int r)
    {
        int i = l;
        for (l += NN, r += NN; l <= r; l >>= 1, r >>= 1)
        {
            if (l & 1)
            {
                if (B[mn[l]] < B[i])
                    i = mn[l];
                ++l;
            }
            if (~r & 1)
            {
                if (B[mn[r]] < B[i])
                    i = mn[r];
                --r;
            }
        }
        return i;
    }
}

void precLR()
{
    vector<int> stk;
    for (int i = 0; i < n; ++i)
    {
        while (!stk.empty() && B[stk.back()] > B[i])
            stk.pop_back();
        leftLeq[i] = !stk.empty() ? stk.back() : -1;
        stk.push_back(i);
    }
    stk = {n};
    for (int i = n - 1; i >= 0; --i)
    {
        while (B[stk.back()] >= B[i])
            stk.pop_back();
        rightLe[i] = stk.back();
        stk.push_back(i);
    }
}

struct fnw
{
    ll f[N];
    fnw() { memset(f, 0, sizeof f); }
    void _add(int i, ll delta)
    {
        for (++i; i < N; i += i & -i)
            f[i] += delta;
    }
    void add(int l, int r, ll delta)
    {
        _add(l, delta);
        _add(r + 1, -delta);
    }
    ll gt(int i)
    {
        ll sum = 0;
        for (++i; i >= 1; i -= i & -i)
            sum += f[i];
        return sum;
    }
} fa, fb;

void solve_task3(vector<Query> qr)
{
    int Q1 = qr.size();
    sort(all(qr), [&](const Query& lhs, const Query& rhs) -> bool
    {
        return lhs.u < rhs.u;
    });
    auto geq = [&](int u)
    {
        int vl = -1;
        int vr = Q1;
        while (vr - vl > 1)
        {
            int vm = (vl + vr) >> 1;
            if (qr[vm].u >= u)
                vr = vm;
            else
                vl = vm;
        }
        return vr;
    };
    auto leq = [&](int u)
    {
        int vl = -1;
        int vr = Q1;
        while (vr - vl > 1)
        {
            int vm = (vl + vr) >> 1;
            if (qr[vm].u <= u)
                vl = vm;
            else
                vr = vm;
        }
        return vl;
    };

    struct Event
    {
        int x;
        int sl, sr;
        ll a, b;

        bool operator < (const Event& oth) const
        {
            return x < oth.x;
        }
    };
    vector<Event> ev;

    auto add = [&](int ul, int ur, int sl, int sr, ll a, ll b)
    {
        ul = geq(ul);
        ur = leq(ur);
        if (ul <= ur)
        {
            ev.push_back({ul, sl, sr, a, b});
            ev.push_back({ur + 1, sl, sr, -a, -b});
        }
    };

    for (int i = 0; i < n; ++i)
    {
        int l = leftLeq[i];
        int r = rightLe[i];

        add(0, X[r] - X[i], l + 1, i, B[i], 0);
        add(X[r] - X[i] + 1, INF32, l + 1, i, 0, B[i] * (X[r] - X[i]));
        add(X[r] - X[i], X[r] - X[l] - 1, 0, l, 0, B[i] * X[r]);
        add(0, X[r] - X[i] - 1, 0, l, B[i], B[i] * X[i]);
        add(0, X[i] - X[l], 0, l, 0, -B[i] * X[i]);
        add(X[i] - X[l] + 1, X[r] - X[l] - 1, 0, l, -B[i], -B[i] * X[l]);
    }
    sort(all(ev));
    int eptr = 0;
    for (int qi = 0; qi < Q1; ++qi)
    {
        for (; eptr < ev.size(); ++eptr)
        {
            auto& e = ev[eptr];
            if (e.x > qi) break;
            fa.add(e.sl, e.sr, e.a);
            fb.add(e.sl, e.sr, e.b);
        }

        auto& q = qr[qi];
        ans[q.idx] += (fa.gt(q.s) * q.u + fb.gt(q.s)) * q.sgn;
    }
}

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> Q;
    X[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> D[i];
        X[i + 1] = X[i] + D[i];
    }
    rmaxq::build(D, n);

    for (int i = 0; i < n; ++i)
    {
        cin >> B[i];
    }
    rminq::build(n);
    B[n] = 0;
    precLR();

    bool task2 = true;
    bool task3 = true;
    for (int j = 0; j < Q; ++j)
    {
        auto& q = qr[j];
        cin >> q.s >> q.t >> q.u;
        --q.s; --q.t;
        q.sgn = 1;
        q.idx = j;
        if (j > 1) task2 &= q.u == qr[0].u;
        task3 &= q.t == n;
        if (rmaxq::gt(q.s, q.t - 1) > q.u)
        {
            ans[q.idx] = -1;
        }
    }


#ifndef DEBUG
    if (task2)
    {
        #define int ll
        ll U = qr[0].u;

        struct Event
        {
            ll x;
            int tp;
            int idx;
            int v;

            bool operator < (const Event& oth) const
            {
                if (x != oth.x) return x > oth.x;
                return tp < oth.tp;
            }
        };
        vector<Event> ev;
        for (int i = 0; i < n; ++i)
        {
            ev.push_back({X[i], 0, i, B[i]});
        }
        for (int j = 0; j < Q; ++j)
        {
            if (ans[j] == -1) continue;
            auto& q = qr[j];
            ev.push_back({X[q.s], 1, j, X[q.t]});
        }
        sort(all(ev));
        vector<pair<int, pll>> st;
        vector<ll> sum;
        for (auto& e : ev)
        {
            if (e.tp == 0)
            {
                while (!st.empty() && st.back().fi >= e.v && st.back().se.se <= e.x + U)
                {
                    sum.pop_back();
                    st.pop_back();
                }
                if (!st.empty() && st.back().fi >= e.v && st.back().se.fi < e.x + U)
                {
                    sum.back() -= st.back().fi * (e.x + U - st.back().se.fi);
                    st.back().se.fi = e.x + U;
                }
                st.push_back({e.v, {e.x, st.empty() ? e.x + U : st.back().se.fi}});
                sum.push_back((sum.empty() ? 0 : sum.back()) + st.back().fi * (st.back().se.se - st.back().se.fi));
            }
            else
            {
                ll x = e.v;
                int sz = st.size();
                int vl = -1;
                int vr = sz;
                while (vr - vl > 1)
                {
                    int vm = (vl + vr) >> 1;
                    if (st[sz - 1 - vm].se.fi <= x)
                        vl = vm;
                    else
                        vr = vm;
                }
                ans[e.idx] = sum.back();
                if (vr < st.size())
                    ans[e.idx] -= sum[sz - 1 - vr];
                if (st[sz - 1 - vl].se.se > x)
                    ans[e.idx] -= st[sz - 1 - vl].fi * (st[sz - 1 - vl].se.se - x);
            }
        }

        for (int j = 0; j < Q; ++j)
            cout << ans[j] << '\n';
        exit(0);
    }
#endif

#ifndef DEBUG
    if (task3)
    {
        vector<Query> q;
        for (int j = 0; j < Q; ++j)
            if (ans[j] != -1)
                q.push_back(qr[j]);

        solve_task3(q);

        for (int j = 0; j < Q; ++j)
            cout << ans[j] << '\n';
        exit(0);
    }
#endif

    vector<Query> q3;
    for (int j = 0; j < Q; ++j)
    {
        if (ans[j] == -1) continue;
        auto q = qr[j];
        q3.push_back(q);
        if (q.t < n)
        {
            int i = lower_bound(X, X + n, X[q.t] - q.u) - X;
            chkmax(i, q.s);
            i = rminq::gt(i, q.t);
            q3.push_back({i, n, j, q.u, -1});
            ans[j] += (X[q.t] - X[i]) * B[i];
        }
    }
    //for (auto& q : q3) debug(q.s, q.t, q.u, q.idx, q.sgn);
    solve_task3(q3);

    for (int j = 0; j < Q; ++j)
        cout << ans[j] << '\n';

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve_task3(std::vector<Query>)':
Main.cpp:231:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<solve_task3(std::vector<Query>)::Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  231 |         for (; eptr < ev.size(); ++eptr)
      |                ~~~~~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:352:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  352 |                 if (vr < st.size())
      |                     ~~~^~~~~~~~~~~

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