Submission #924018

#	Time	Username	Problem	Language	Result	Execution time	Memory
924018		vjudge1	Fire (JOI20_ho_t5)	C++17	100 / 100	765 ms	107444 KiB

ho_t5

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>

#include <bits/stdc++.h>
#include <chrono>
#include <random>

// @author: Vlapos

namespace operators
{
    template <typename T1, typename T2>
    std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
    {
        in >> x.first >> x.second;
        return in;
    }

    template <typename T1, typename T2>
    std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
    {
        out << x.first << " " << x.second;
        return out;
    }

    template <typename T1>
    std::istream &operator>>(std::istream &in, std::vector<T1> &x)
    {
        for (auto &i : x)
            in >> i;
        return in;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }

    template <typename T1>
    std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
    {
        for (auto &i : x)
            out << i << " ";
        return out;
    }
}

// name spaces
using namespace std;
using namespace operators;
// end of name spaces

// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines

// usefull stuff

void boost()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }

const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};

const ll INF = (1e15) + 500;
const int BIG = (2e9) + 500;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;

// #define int ll

struct segTreeAdd
{
    vector<pll> tree;
    int sz;

    void init(int n)
    {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.resize(2 * sz, {0, 0});
    }

    void upd(int v, int lv, int rv, ll val)
    {
        tree[v].s += val;
        tree[v].f += (ll)(rv - lv) * (ll)val;
    }

    void push(int v, int lv, int rv)
    {
        if (rv - lv == 1 or tree[v].s == 0)
            return;

        int m = (lv + rv) >> 1;
        upd(v * 2 + 1, lv, m, tree[v].s);
        upd(v * 2 + 2, m, rv, tree[v].s);
        tree[v].s = 0;
    }

    void update(int l, int r, ll val, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (l <= lv and rv <= r)
        {
            upd(v, lv, rv, val);
            return;
        }
        if (rv <= l or r <= lv)
            return;
        int m = (lv + rv) >> 1;
        update(l, r, val, v * 2 + 1, lv, m);
        update(l, r, val, v * 2 + 2, m, rv);
        tree[v].f = tree[v * 2 + 1].f + tree[v * 2 + 2].f;
    }

    void update(int l, int r, ll val)
    {
        update(l, r, val, 0, 0, sz);
    }

    ll get(int l, int r, int v, int lv, int rv)
    {
        push(v, lv, rv);
        if (l <= lv and rv <= r)
            return tree[v].f;
        if (rv <= l or r <= lv)
            return 0;
        int m = (lv + rv) >> 1;
        return get(l, r, v * 2 + 1, lv, m) + get(l, r, v * 2 + 2, m, rv);
    }

    ll get(int l, int r)
    {
        return get(l, r, 0, 0, sz);
    }
};

struct test
{
    struct op
    {
        int t, l, r, val;
    };

    vector<vector<op>> reqs;
    int n, q;

    void addTriangle(int l, int r, int val)
    {
        if (l >= r)
            return;
        reqs[0].push_back({0, 0, n - l + 1, +val});
        reqs[0].push_back({1, r, n, -val});
        reqs[r - l].push_back({1, r, n, +val});
        reqs[r - l].push_back({0, 0, n - l + 1, -val});
    }

    void solve(int testcase)
    {
        boost();

        cin >> n >> q;

        vector<int> a(n), L(n);
        cin >> a;

        reqs.resize(3 * n + 10);

        {
            stack<int> bf;
            for (int i = 0; i < n; ++i)
            {
                while (bf.size() and a[bf.top()] <= a[i])
                    bf.pop();

                if (bf.size())
                    L[i] = bf.top();
                else
                    L[i] = i - n - 3;
                bf.push(i);
            }
        }

        {
            stack<int> bf;
            for (int i = n - 1; i >= 0; --i)
            {
                while (bf.size() and a[bf.top()] < a[i])
                    bf.pop();

                int curL = L[i] + 1;
                int curR = bf.size() ? bf.top() : n;
                addTriangle(curL, curR, a[i]); // [L, R)
                addTriangle(curL, i, -a[i]);   // [L, R)
                addTriangle(i + 1, curR, -a[i]);

                bf.push(i);
            }
        }

        vector<vector<pair<int, pii>>> qrs(n + 10 + 10);
        vector<ll> ans(q);
        for (int i = 0; i < q; ++i)
        {
            int t, l, r;
            cin >> t >> l >> r;
            --l;
            qrs[t].pb({i, {l, r}});
        }

        segTreeAdd diag, square;

        diag.init(n * 3 + 10);
        square.init(n + 100);

        for (int t = 0; t <= n; ++t)
        {
            for (op req : reqs[t])
            {
                if (req.t == 0)
                    // triangle
                    diag.update(req.l, req.r, req.val);
                else
                    // square
                    square.update(req.l, req.r, req.val);
            }

            // for (int i = 0; i < n; ++i)
            // {
            //     cout << diag.get(n - i + t, n - i + t + 1) + square.get(i, i + 1) << ' ';
            // }
            // cout << "\n";

            for (auto &[id, seg] : qrs[t])
            {
                auto [l, r] = seg;
                ans[id] = diag.get(n - (r - 1) + t, n - l + t + 1) + square.get(l, r);
            }
        }

        for (int i = 0; i < q; ++i)
            cout << ans[i] << "\n";
    }
};

main()
{
    boost();
    int q = 1;
    // cin >> q;
    for (int i = 0; i < q; i++)
    {
        test t;
        t.solve(i);
    }
    return 0;
}
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
//                                                                                    //
//                               Coded by Der_Vlἀpos                                  //
//                                                                                    //
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//

Compilation message (stderr)

ho_t5.cpp:270:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  270 | main()
      | ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80