oj.uz

Submission #924018

# Submission time Handle Problem Language Result Execution time Memory
924018 2024-02-08T09:31:05 Z vjudge1 Fire (JOI20_ho_t5) C++17
100 / 100
 765 ms 107444 KB 
// #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

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 572 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 456 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 360 KB Output is correct
31 Correct 1 ms 352 KB Output is correct
32 Correct 1 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 701 ms 103552 KB Output is correct
3 Correct 640 ms 100680 KB Output is correct
4 Correct 662 ms 102284 KB Output is correct
5 Correct 689 ms 105536 KB Output is correct
6 Correct 699 ms 102984 KB Output is correct
7 Correct 679 ms 102292 KB Output is correct
8 Correct 708 ms 105504 KB Output is correct
9 Correct 711 ms 104876 KB Output is correct
10 Correct 681 ms 100936 KB Output is correct
11 Correct 691 ms 103256 KB Output is correct
12 Correct 691 ms 102316 KB Output is correct
13 Correct 705 ms 107444 KB Output is correct
14 Correct 667 ms 105988 KB Output is correct
15 Correct 673 ms 103852 KB Output is correct
16 Correct 677 ms 103388 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 674 ms 99540 KB Output is correct
3 Correct 652 ms 98768 KB Output is correct
4 Correct 662 ms 104104 KB Output is correct
5 Correct 654 ms 98440 KB Output is correct
6 Correct 680 ms 98480 KB Output is correct
7 Correct 667 ms 101036 KB Output is correct
8 Correct 666 ms 98744 KB Output is correct
9 Correct 637 ms 98696 KB Output is correct
10 Correct 668 ms 98548 KB Output is correct
11 Correct 703 ms 104736 KB Output is correct
12 Correct 671 ms 103340 KB Output is correct
13 Correct 667 ms 102012 KB Output is correct
14 Correct 688 ms 99248 KB Output is correct
15 Correct 683 ms 100420 KB Output is correct
16 Correct 654 ms 102296 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 98292 KB Output is correct
2 Correct 614 ms 98952 KB Output is correct
3 Correct 619 ms 99752 KB Output is correct
4 Correct 616 ms 99436 KB Output is correct
5 Correct 580 ms 98476 KB Output is correct
6 Correct 597 ms 98312 KB Output is correct
7 Correct 614 ms 97992 KB Output is correct
8 Correct 622 ms 98048 KB Output is correct
9 Correct 605 ms 96924 KB Output is correct
10 Correct 600 ms 97000 KB Output is correct
11 Correct 601 ms 97796 KB Output is correct
12 Correct 592 ms 96996 KB Output is correct
13 Correct 608 ms 99052 KB Output is correct
14 Correct 595 ms 97624 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 572 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 456 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 360 KB Output is correct
31 Correct 1 ms 352 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 701 ms 103552 KB Output is correct
34 Correct 640 ms 100680 KB Output is correct
35 Correct 662 ms 102284 KB Output is correct
36 Correct 689 ms 105536 KB Output is correct
37 Correct 699 ms 102984 KB Output is correct
38 Correct 679 ms 102292 KB Output is correct
39 Correct 708 ms 105504 KB Output is correct
40 Correct 711 ms 104876 KB Output is correct
41 Correct 681 ms 100936 KB Output is correct
42 Correct 691 ms 103256 KB Output is correct
43 Correct 691 ms 102316 KB Output is correct
44 Correct 705 ms 107444 KB Output is correct
45 Correct 667 ms 105988 KB Output is correct
46 Correct 673 ms 103852 KB Output is correct
47 Correct 677 ms 103388 KB Output is correct
48 Correct 674 ms 99540 KB Output is correct
49 Correct 652 ms 98768 KB Output is correct
50 Correct 662 ms 104104 KB Output is correct
51 Correct 654 ms 98440 KB Output is correct
52 Correct 680 ms 98480 KB Output is correct
53 Correct 667 ms 101036 KB Output is correct
54 Correct 666 ms 98744 KB Output is correct
55 Correct 637 ms 98696 KB Output is correct
56 Correct 668 ms 98548 KB Output is correct
57 Correct 703 ms 104736 KB Output is correct
58 Correct 671 ms 103340 KB Output is correct
59 Correct 667 ms 102012 KB Output is correct
60 Correct 688 ms 99248 KB Output is correct
61 Correct 683 ms 100420 KB Output is correct
62 Correct 654 ms 102296 KB Output is correct
63 Correct 596 ms 98292 KB Output is correct
64 Correct 614 ms 98952 KB Output is correct
65 Correct 619 ms 99752 KB Output is correct
66 Correct 616 ms 99436 KB Output is correct
67 Correct 580 ms 98476 KB Output is correct
68 Correct 597 ms 98312 KB Output is correct
69 Correct 614 ms 97992 KB Output is correct
70 Correct 622 ms 98048 KB Output is correct
71 Correct 605 ms 96924 KB Output is correct
72 Correct 600 ms 97000 KB Output is correct
73 Correct 601 ms 97796 KB Output is correct
74 Correct 592 ms 96996 KB Output is correct
75 Correct 608 ms 99052 KB Output is correct
76 Correct 595 ms 97624 KB Output is correct
77 Correct 732 ms 100944 KB Output is correct
78 Correct 731 ms 101836 KB Output is correct
79 Correct 744 ms 104260 KB Output is correct
80 Correct 728 ms 100768 KB Output is correct
81 Correct 712 ms 99876 KB Output is correct
82 Correct 765 ms 102536 KB Output is correct
83 Correct 735 ms 102604 KB Output is correct
84 Correct 735 ms 100464 KB Output is correct
85 Correct 748 ms 106052 KB Output is correct
86 Correct 731 ms 99600 KB Output is correct
87 Correct 707 ms 100984 KB Output is correct
88 Correct 696 ms 105896 KB Output is correct
89 Correct 697 ms 98860 KB Output is correct
90 Correct 719 ms 104672 KB Output is correct
91 Correct 709 ms 100012 KB Output is correct
92 Correct 699 ms 99756 KB Output is correct
93 Correct 707 ms 98736 KB Output is correct
94 Correct 713 ms 104128 KB Output is correct
95 Correct 699 ms 105128 KB Output is correct
96 Correct 680 ms 98888 KB Output is correct
97 Correct 710 ms 100716 KB Output is correct
98 Correct 708 ms 98220 KB Output is correct
99 Correct 671 ms 102000 KB Output is correct
100 Correct 741 ms 101280 KB Output is correct
101 Correct 723 ms 95908 KB Output is correct
102 Correct 734 ms 100884 KB Output is correct