oj.uz

Submission #541146

# Submission time Handle Problem Language Result Execution time Memory
541146 2022-03-22T11:34:54 Z LittleCube Fire (JOI20_ho_t5) C++14
14 / 100
 1000 ms 70684 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()
{
    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:120: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]
  120 |         while (rdx < regularmodifies.size() && regularmodifies[rdx].F == i)
      |                ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ho_t5.cpp:125: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]
  125 |         while (odx < offmodifies.size() && offmodifies[odx].F == i)
      |                ~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 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 1 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 2 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 2 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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 900 ms 68056 KB Output is correct
3 Correct 895 ms 69460 KB Output is correct
4 Correct 935 ms 65876 KB Output is correct
5 Correct 907 ms 68500 KB Output is correct
6 Correct 887 ms 65356 KB Output is correct
7 Correct 994 ms 67816 KB Output is correct
8 Correct 910 ms 67240 KB Output is correct
9 Correct 964 ms 67924 KB Output is correct
10 Correct 910 ms 67076 KB Output is correct
11 Correct 955 ms 69484 KB Output is correct
12 Correct 904 ms 67544 KB Output is correct
13 Execution timed out 1004 ms 65652 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 952 ms 69296 KB Output is correct
3 Correct 848 ms 67984 KB Output is correct
4 Correct 853 ms 70684 KB Output is correct
5 Correct 834 ms 68840 KB Output is correct
6 Correct 826 ms 69448 KB Output is correct
7 Correct 816 ms 69768 KB Output is correct
8 Correct 864 ms 69024 KB Output is correct
9 Correct 818 ms 68348 KB Output is correct
10 Correct 818 ms 67668 KB Output is correct
11 Correct 849 ms 70584 KB Output is correct
12 Correct 852 ms 69984 KB Output is correct
13 Correct 829 ms 70244 KB Output is correct
14 Correct 823 ms 68584 KB Output is correct
15 Correct 884 ms 70648 KB Output is correct
16 Correct 841 ms 70032 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 60292 KB Output is correct
2 Correct 742 ms 64768 KB Output is correct
3 Correct 760 ms 66276 KB Output is correct
4 Correct 766 ms 64400 KB Output is correct
5 Correct 725 ms 64604 KB Output is correct
6 Correct 772 ms 64860 KB Output is correct
7 Correct 743 ms 66028 KB Output is correct
8 Correct 734 ms 65424 KB Output is correct
9 Correct 742 ms 64608 KB Output is correct
10 Correct 736 ms 65356 KB Output is correct
11 Correct 756 ms 64872 KB Output is correct
12 Correct 757 ms 65200 KB Output is correct
13 Correct 757 ms 64800 KB Output is correct
14 Correct 793 ms 64996 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 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 1 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 2 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 2 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 900 ms 68056 KB Output is correct
34 Correct 895 ms 69460 KB Output is correct
35 Correct 935 ms 65876 KB Output is correct
36 Correct 907 ms 68500 KB Output is correct
37 Correct 887 ms 65356 KB Output is correct
38 Correct 994 ms 67816 KB Output is correct
39 Correct 910 ms 67240 KB Output is correct
40 Correct 964 ms 67924 KB Output is correct
41 Correct 910 ms 67076 KB Output is correct
42 Correct 955 ms 69484 KB Output is correct
43 Correct 904 ms 67544 KB Output is correct
44 Execution timed out 1004 ms 65652 KB Time limit exceeded
45 Halted 0 ms 0 KB -