oj.uz

Submission #381161

# Submission time Handle Problem Language Result Execution time Memory
381161 2021-03-24T16:37:50 Z usachevd0 Dungeon 3 (JOI21_ho_t5) C++14
100 / 100
 1059 ms 146648 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11940 KB Output is correct
2 Correct 20 ms 11940 KB Output is correct
3 Correct 17 ms 11940 KB Output is correct
4 Correct 19 ms 11940 KB Output is correct
5 Correct 22 ms 11940 KB Output is correct
6 Correct 36 ms 11940 KB Output is correct
7 Correct 32 ms 11940 KB Output is correct
8 Correct 19 ms 11940 KB Output is correct
9 Correct 24 ms 11940 KB Output is correct
10 Correct 19 ms 11940 KB Output is correct
11 Correct 16 ms 11940 KB Output is correct
12 Correct 16 ms 11940 KB Output is correct
13 Correct 26 ms 12068 KB Output is correct
14 Correct 25 ms 11940 KB Output is correct
15 Correct 19 ms 11940 KB Output is correct
16 Correct 19 ms 11892 KB Output is correct
17 Correct 36 ms 11812 KB Output is correct
18 Correct 18 ms 11748 KB Output is correct
19 Correct 21 ms 11788 KB Output is correct
20 Correct 15 ms 11248 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 22492 KB Output is correct
2 Correct 72 ms 20648 KB Output is correct
3 Correct 78 ms 22624 KB Output is correct
4 Correct 76 ms 22496 KB Output is correct
5 Correct 84 ms 20012 KB Output is correct
6 Correct 344 ms 60748 KB Output is correct
7 Correct 327 ms 52796 KB Output is correct
8 Correct 395 ms 61596 KB Output is correct
9 Correct 384 ms 61612 KB Output is correct
10 Correct 396 ms 60476 KB Output is correct
11 Correct 361 ms 60036 KB Output is correct
12 Correct 427 ms 60908 KB Output is correct
13 Correct 269 ms 49752 KB Output is correct
14 Correct 264 ms 49932 KB Output is correct
15 Correct 222 ms 59476 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 131604 KB Output is correct
2 Correct 650 ms 131520 KB Output is correct
3 Correct 713 ms 131240 KB Output is correct
4 Correct 962 ms 132384 KB Output is correct
5 Correct 660 ms 130956 KB Output is correct
6 Correct 654 ms 130952 KB Output is correct
7 Correct 889 ms 128112 KB Output is correct
8 Correct 590 ms 127900 KB Output is correct
9 Correct 649 ms 128332 KB Output is correct
10 Correct 485 ms 89472 KB Output is correct
11 Correct 758 ms 127860 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11940 KB Output is correct
2 Correct 20 ms 11940 KB Output is correct
3 Correct 17 ms 11940 KB Output is correct
4 Correct 19 ms 11940 KB Output is correct
5 Correct 22 ms 11940 KB Output is correct
6 Correct 36 ms 11940 KB Output is correct
7 Correct 32 ms 11940 KB Output is correct
8 Correct 19 ms 11940 KB Output is correct
9 Correct 24 ms 11940 KB Output is correct
10 Correct 19 ms 11940 KB Output is correct
11 Correct 16 ms 11940 KB Output is correct
12 Correct 16 ms 11940 KB Output is correct
13 Correct 26 ms 12068 KB Output is correct
14 Correct 25 ms 11940 KB Output is correct
15 Correct 19 ms 11940 KB Output is correct
16 Correct 19 ms 11892 KB Output is correct
17 Correct 36 ms 11812 KB Output is correct
18 Correct 18 ms 11748 KB Output is correct
19 Correct 21 ms 11788 KB Output is correct
20 Correct 15 ms 11248 KB Output is correct
21 Correct 164 ms 22492 KB Output is correct
22 Correct 72 ms 20648 KB Output is correct
23 Correct 78 ms 22624 KB Output is correct
24 Correct 76 ms 22496 KB Output is correct
25 Correct 84 ms 20012 KB Output is correct
26 Correct 344 ms 60748 KB Output is correct
27 Correct 327 ms 52796 KB Output is correct
28 Correct 395 ms 61596 KB Output is correct
29 Correct 384 ms 61612 KB Output is correct
30 Correct 396 ms 60476 KB Output is correct
31 Correct 361 ms 60036 KB Output is correct
32 Correct 427 ms 60908 KB Output is correct
33 Correct 269 ms 49752 KB Output is correct
34 Correct 264 ms 49932 KB Output is correct
35 Correct 222 ms 59476 KB Output is correct
36 Correct 985 ms 131604 KB Output is correct
37 Correct 650 ms 131520 KB Output is correct
38 Correct 713 ms 131240 KB Output is correct
39 Correct 962 ms 132384 KB Output is correct
40 Correct 660 ms 130956 KB Output is correct
41 Correct 654 ms 130952 KB Output is correct
42 Correct 889 ms 128112 KB Output is correct
43 Correct 590 ms 127900 KB Output is correct
44 Correct 649 ms 128332 KB Output is correct
45 Correct 485 ms 89472 KB Output is correct
46 Correct 758 ms 127860 KB Output is correct
47 Correct 1041 ms 145272 KB Output is correct
48 Correct 786 ms 145020 KB Output is correct
49 Correct 774 ms 145356 KB Output is correct
50 Correct 1059 ms 146648 KB Output is correct
51 Correct 873 ms 146256 KB Output is correct
52 Correct 859 ms 146332 KB Output is correct
53 Correct 912 ms 139648 KB Output is correct
54 Correct 732 ms 139600 KB Output is correct
55 Correct 790 ms 139460 KB Output is correct
56 Correct 566 ms 106428 KB Output is correct
57 Correct 749 ms 138024 KB Output is correct