oj.uz

Submission #541147

# Submission time Handle Problem Language Result Execution time Memory
541147 2022-03-22T11:36:13 Z LittleCube Fire (JOI20_ho_t5) C++14
100 / 100
 732 ms 77788 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

struct query
{
    int i, T, L, R;
};

struct SegTree
{
    const static int N = 400005;
    ll seg[4 * N + 5], lazy[4 * N + 5];
    void modify(int pos, ll val, int i = 1, int L = 1, int R = N)
    {
        if (pos <= L)
            lazy[i] += val;
        else if (R < pos)
            return;
        else
        {
            int mid = (L + R) / 2;
            lazy[i * 2] += lazy[i];
            lazy[i * 2 + 1] += lazy[i];
            lazy[i] = 0;
            modify(pos, val, i * 2, L, mid);
            modify(pos, val, i * 2 + 1, mid + 1, R);
            seg[i] = seg[i * 2] + lazy[i * 2] * (mid - L + 1) +
                     seg[i * 2 + 1] + lazy[i * 2 + 1] * (R - mid);
        }
    }
    ll query(int qL, int qR, int i = 1, int L = 1, int R = N)
    {
        if (qL <= L && R <= qR)
            return seg[i] + (R - L + 1) * lazy[i];
        else if (R < qL || qR < L)
            return 0;
        else
        {
            int mid = (L + R) / 2;
            seg[i] += (R - L + 1) * lazy[i];
            lazy[i * 2] += lazy[i];
            lazy[i * 2 + 1] += lazy[i];
            lazy[i] = 0;
            return query(qL, qR, i * 2, L, mid) + query(qL, qR, i * 2 + 1, mid + 1, R);
        }
    }
};

ll N, Q, arr[200005], ans[200005], front[200005], back[200005];
SegTree reg, off;
query q[200005];

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> Q;
    for (int i = 1; i <= N; i++)
        cin >> arr[i];
    for (int i = 1; i <= Q; i++)
    {
        cin >> q[i].T >> q[i].L >> q[i].R;
        q[i].i = i;
    }
    sort(q + 1, q + 1 + Q, [](query q1, query q2)
         { return q1.T < q2.T; });

    int qdx = 1, odx = 0, rdx = 0;
    vector<pair<int, pll>> offmodifies, regularmodifies;
    vector<int> mono;

    auto triangle = [&](int x, int y, ll val)
    {
        regularmodifies.emplace_back(pair<int, pll>{y, {x, val}});
        offmodifies.emplace_back(pair<int, pll>{y, {x + N - y, -val}});
    };

    for (int i = 1; i <= N; i++)
        triangle(i, 0, arr[i]);

    mono.clear();
    for (int i = 1; i <= N; i++)
    {
        while (!mono.empty() && arr[mono.back()] < arr[i])
            mono.pop_back();
        if (!mono.empty())
        {
            triangle(i, i - mono.back(), -arr[i]);
            front[i] = mono.back();
        }
        mono.emplace_back(i);
    }

    mono.clear();
    for (int i = N; i >= 1; i--)
    {
        while (!mono.empty() && arr[mono.back()] <= arr[i])
            mono.pop_back();
        if (!mono.empty())
        {
            triangle(mono.back(), mono.back() - i, -arr[i]);
            back[i] = mono.back();
        }
        mono.emplace_back(i);
    }

    for (int i = 1; i <= N; i++)
        if (front[i] && back[i])
            triangle(back[i], back[i] - front[i], arr[i]);
    sort(regularmodifies.begin(), regularmodifies.end());
    sort(offmodifies.begin(), offmodifies.end());

    for (int i = 0; i <= N; i++)
    {
        while (rdx < regularmodifies.size() && regularmodifies[rdx].F == i)
        {
            reg.modify(regularmodifies[rdx].S.F, regularmodifies[rdx].S.S);
            rdx++;
        }
        while (odx < offmodifies.size() && offmodifies[odx].F == i)
        {
            off.modify(offmodifies[odx].S.F, offmodifies[odx].S.S);
            odx++;
        }

        while (qdx <= Q && q[qdx].T == i)
        {
            ans[q[qdx].i] = reg.query(q[qdx].L, q[qdx].R) + off.query(N - i - 1 + q[qdx].L, N - i - 1 + q[qdx].R);
            qdx++;
        }
    }
    for (int i = 1; i <= Q; i++)
        cout << ans[i] << '\n';
}

/*
4 1 1
4 2 2
4 3 3
4 4 4
4 5 5
*/

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:121:20: warning: comparison of integer expressions of different signedness: '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]
  121 |         while (rdx < regularmodifies.size() && regularmodifies[rdx].F == i)
      |                ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ho_t5.cpp:126:20: warning: comparison of integer expressions of different signedness: '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]
  126 |         while (odx < offmodifies.size() && offmodifies[odx].F == i)
      |                ~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 687 ms 68072 KB Output is correct
3 Correct 665 ms 69380 KB Output is correct
4 Correct 692 ms 65840 KB Output is correct
5 Correct 667 ms 68372 KB Output is correct
6 Correct 695 ms 65264 KB Output is correct
7 Correct 689 ms 67904 KB Output is correct
8 Correct 710 ms 67344 KB Output is correct
9 Correct 726 ms 67892 KB Output is correct
10 Correct 679 ms 67088 KB Output is correct
11 Correct 704 ms 69464 KB Output is correct
12 Correct 670 ms 67636 KB Output is correct
13 Correct 674 ms 65536 KB Output is correct
14 Correct 679 ms 67516 KB Output is correct
15 Correct 687 ms 67564 KB Output is correct
16 Correct 680 ms 65412 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 635 ms 69296 KB Output is correct
3 Correct 608 ms 68276 KB Output is correct
4 Correct 662 ms 70968 KB Output is correct
5 Correct 632 ms 68784 KB Output is correct
6 Correct 669 ms 69500 KB Output is correct
7 Correct 672 ms 69732 KB Output is correct
8 Correct 663 ms 68996 KB Output is correct
9 Correct 703 ms 68588 KB Output is correct
10 Correct 669 ms 68144 KB Output is correct
11 Correct 712 ms 70828 KB Output is correct
12 Correct 689 ms 70184 KB Output is correct
13 Correct 639 ms 70516 KB Output is correct
14 Correct 613 ms 68868 KB Output is correct
15 Correct 636 ms 70764 KB Output is correct
16 Correct 632 ms 70360 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 60612 KB Output is correct
2 Correct 594 ms 60936 KB Output is correct
3 Correct 579 ms 62224 KB Output is correct
4 Correct 578 ms 60208 KB Output is correct
5 Correct 597 ms 60736 KB Output is correct
6 Correct 581 ms 61108 KB Output is correct
7 Correct 573 ms 62084 KB Output is correct
8 Correct 575 ms 61436 KB Output is correct
9 Correct 603 ms 60576 KB Output is correct
10 Correct 578 ms 61500 KB Output is correct
11 Correct 589 ms 60808 KB Output is correct
12 Correct 601 ms 61220 KB Output is correct
13 Correct 577 ms 60856 KB Output is correct
14 Correct 601 ms 60976 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Correct 687 ms 68072 KB Output is correct
34 Correct 665 ms 69380 KB Output is correct
35 Correct 692 ms 65840 KB Output is correct
36 Correct 667 ms 68372 KB Output is correct
37 Correct 695 ms 65264 KB Output is correct
38 Correct 689 ms 67904 KB Output is correct
39 Correct 710 ms 67344 KB Output is correct
40 Correct 726 ms 67892 KB Output is correct
41 Correct 679 ms 67088 KB Output is correct
42 Correct 704 ms 69464 KB Output is correct
43 Correct 670 ms 67636 KB Output is correct
44 Correct 674 ms 65536 KB Output is correct
45 Correct 679 ms 67516 KB Output is correct
46 Correct 687 ms 67564 KB Output is correct
47 Correct 680 ms 65412 KB Output is correct
48 Correct 635 ms 69296 KB Output is correct
49 Correct 608 ms 68276 KB Output is correct
50 Correct 662 ms 70968 KB Output is correct
51 Correct 632 ms 68784 KB Output is correct
52 Correct 669 ms 69500 KB Output is correct
53 Correct 672 ms 69732 KB Output is correct
54 Correct 663 ms 68996 KB Output is correct
55 Correct 703 ms 68588 KB Output is correct
56 Correct 669 ms 68144 KB Output is correct
57 Correct 712 ms 70828 KB Output is correct
58 Correct 689 ms 70184 KB Output is correct
59 Correct 639 ms 70516 KB Output is correct
60 Correct 613 ms 68868 KB Output is correct
61 Correct 636 ms 70764 KB Output is correct
62 Correct 632 ms 70360 KB Output is correct
63 Correct 594 ms 60612 KB Output is correct
64 Correct 594 ms 60936 KB Output is correct
65 Correct 579 ms 62224 KB Output is correct
66 Correct 578 ms 60208 KB Output is correct
67 Correct 597 ms 60736 KB Output is correct
68 Correct 581 ms 61108 KB Output is correct
69 Correct 573 ms 62084 KB Output is correct
70 Correct 575 ms 61436 KB Output is correct
71 Correct 603 ms 60576 KB Output is correct
72 Correct 578 ms 61500 KB Output is correct
73 Correct 589 ms 60808 KB Output is correct
74 Correct 601 ms 61220 KB Output is correct
75 Correct 577 ms 60856 KB Output is correct
76 Correct 601 ms 60976 KB Output is correct
77 Correct 718 ms 75508 KB Output is correct
78 Correct 732 ms 76692 KB Output is correct
79 Correct 715 ms 76788 KB Output is correct
80 Correct 713 ms 75476 KB Output is correct
81 Correct 709 ms 75208 KB Output is correct
82 Correct 722 ms 76204 KB Output is correct
83 Correct 714 ms 75948 KB Output is correct
84 Correct 710 ms 74928 KB Output is correct
85 Correct 708 ms 76812 KB Output is correct
86 Correct 683 ms 75300 KB Output is correct
87 Correct 716 ms 77112 KB Output is correct
88 Correct 700 ms 77112 KB Output is correct
89 Correct 685 ms 74708 KB Output is correct
90 Correct 710 ms 76784 KB Output is correct
91 Correct 684 ms 75556 KB Output is correct
92 Correct 689 ms 74516 KB Output is correct
93 Correct 695 ms 75820 KB Output is correct
94 Correct 716 ms 77788 KB Output is correct
95 Correct 720 ms 77176 KB Output is correct
96 Correct 708 ms 75992 KB Output is correct
97 Correct 713 ms 76020 KB Output is correct
98 Correct 687 ms 69620 KB Output is correct
99 Correct 695 ms 70516 KB Output is correct
100 Correct 715 ms 70800 KB Output is correct
101 Correct 701 ms 70072 KB Output is correct
102 Correct 729 ms 71480 KB Output is correct