oj.uz

Submission #986501

# Submission time Handle Problem Language Result Execution time Memory
986501 2024-05-20T16:47:19 Z boris_mihov Fish 3 (JOI24_fish3) C++17
100 / 100
 584 ms 62232 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 300000 + 10;
const llong INF = 4e18;

int n, q;
llong d;

struct SegmentTree
{
    struct Node
    {
        llong sumD;
        llong minH;
        llong lazy;

        Node()
        {
            sumD = minH = lazy = 0;
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            Node result;
            result.sumD = left.sumD + right.sumD;
            result.minH = std::min(left.minH, right.minH);
            return result;
        }
    };

    Node tree[4*MAXN];
    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }

        tree[node].sumD += tree[node].lazy * (r - l + 1); 
        tree[node].minH -= tree[node].lazy * d;

        if (l < r)
        {
            tree[2*node].lazy += tree[node].lazy;
            tree[2*node + 1].lazy += tree[node].lazy;
        }

        tree[node].lazy = 0;
    }

    void activate(int l, int r, int node, int queryPos, llong value)
    {
        push(node, l, r);
        if (r < queryPos || queryPos < l)
        {
            return;
        }

        if (l == r)
        {
            tree[node].minH = value;
            return;
        }

        int mid = l + r >> 1;
        activate(l, mid, 2*node, queryPos, value);
        activate(mid + 1, r, 2*node + 1, queryPos, value);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    void update(int l, int r, int node, int queryL, int queryR, llong queryVal)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy = queryVal;
            push(node, l, r);
            return;
        }

        int mid = l + r >> 1;
        update(l, mid, 2*node, queryL, queryR, queryVal);
        update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    Node query(int l, int r, int node, int queryL, int queryR)
    {
        push(node, l, r);
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        Node result;
        int mid = l + r >> 1;
        if (queryL <= mid) result = query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) result = result + query(mid + 1, r, 2*node + 1, queryL, queryR);
        return result;
    }

    void activate(int pos, llong value)
    {
        activate(1, n - 1, 1, pos, value);
    }

    void update(int l, int r, llong val)
    {
        update(1, n - 1, 1, l, r, val);
    }

    llong query(int l, int r)
    {
        if (l == r)
        {
            return 0;
        }

        Node res = query(1, n - 1, 1, l, r - 1);
        if (res.minH < 0) return -1;
        return res.sumD;
    }
};

llong a[MAXN];
llong answer[MAXN];
std::vector <std::pair <int,llong>> reserve;
std::vector <std::pair <int,int>> v[MAXN];
SegmentTree tree;

void solve()
{
    reserve.push_back({0, INF});
    for (int i = 2 ; i <= n ; ++i)
    {
        tree.activate(i - 1, a[i - 1]);
        if (a[i] >= a[i - 1])
        {
            reserve.push_back({i - 1, ((a[i] - a[i - 1]) / d)});
        } else
        {
            llong times = (a[i - 1] - a[i]) / d + (((a[i - 1] - a[i]) % d > 0));
            llong rPos = i;
            while (times > 0)
            {
                auto &[lPos, curr] = reserve.back();
                tree.update(lPos + 1, rPos - 1, times);
                llong min = std::min(curr, times);
                curr -= min;
                times -= min;

                if (curr == 0)
                {
                    rPos = lPos + 1;
                    reserve.pop_back();
                }
            }
        }

        for (const auto &[l, idx] : v[i])
        {
            answer[idx] = tree.query(l, i);
        }
    }
}

void print()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << answer[i] << '\n';
    }
}

void input()
{
    std::cin >> n >> d;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }

    std::cin >> q;
    for (int i = 1 ; i <= q ; ++i)
    {
        int l, r;
        std::cin >> l >> r;
        v[r].push_back({l, i});
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

Compilation message

Main.cpp: In member function 'void SegmentTree::activate(int, int, int, int, llong)':
Main.cpp:70:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, llong)':
Main.cpp:91:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'SegmentTree::Node SegmentTree::query(int, int, int, int, int)':
Main.cpp:106:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35672 KB Output is correct
2 Correct 21 ms 35676 KB Output is correct
3 Correct 18 ms 35488 KB Output is correct
4 Correct 25 ms 35676 KB Output is correct
5 Correct 27 ms 35692 KB Output is correct
6 Correct 19 ms 35848 KB Output is correct
7 Correct 18 ms 35760 KB Output is correct
8 Correct 18 ms 35672 KB Output is correct
9 Correct 24 ms 35672 KB Output is correct
10 Correct 20 ms 35824 KB Output is correct
11 Correct 17 ms 35672 KB Output is correct
12 Correct 16 ms 35932 KB Output is correct
13 Correct 20 ms 35788 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 53700 KB Output is correct
2 Correct 415 ms 55212 KB Output is correct
3 Correct 142 ms 45692 KB Output is correct
4 Correct 458 ms 51548 KB Output is correct
5 Correct 442 ms 51536 KB Output is correct
6 Correct 377 ms 55012 KB Output is correct
7 Correct 408 ms 54900 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 49504 KB Output is correct
2 Correct 504 ms 59116 KB Output is correct
3 Correct 488 ms 59392 KB Output is correct
4 Correct 477 ms 59132 KB Output is correct
5 Correct 526 ms 59120 KB Output is correct
6 Correct 490 ms 52908 KB Output is correct
7 Correct 406 ms 52988 KB Output is correct
8 Correct 402 ms 56136 KB Output is correct
9 Correct 434 ms 56184 KB Output is correct
10 Correct 488 ms 62188 KB Output is correct
11 Correct 396 ms 62172 KB Output is correct
12 Correct 441 ms 59656 KB Output is correct
13 Correct 460 ms 59708 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 52424 KB Output is correct
2 Correct 422 ms 53132 KB Output is correct
3 Correct 302 ms 49140 KB Output is correct
4 Correct 485 ms 56316 KB Output is correct
5 Correct 436 ms 58060 KB Output is correct
6 Correct 579 ms 59092 KB Output is correct
7 Correct 503 ms 57220 KB Output is correct
8 Correct 584 ms 59108 KB Output is correct
9 Correct 387 ms 52304 KB Output is correct
10 Correct 428 ms 52040 KB Output is correct
11 Correct 506 ms 56360 KB Output is correct
12 Correct 470 ms 55516 KB Output is correct
13 Correct 515 ms 58836 KB Output is correct
14 Correct 509 ms 54732 KB Output is correct
15 Correct 432 ms 58776 KB Output is correct
16 Correct 449 ms 54636 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35672 KB Output is correct
2 Correct 21 ms 35676 KB Output is correct
3 Correct 18 ms 35488 KB Output is correct
4 Correct 25 ms 35676 KB Output is correct
5 Correct 27 ms 35692 KB Output is correct
6 Correct 19 ms 35848 KB Output is correct
7 Correct 18 ms 35760 KB Output is correct
8 Correct 18 ms 35672 KB Output is correct
9 Correct 24 ms 35672 KB Output is correct
10 Correct 20 ms 35824 KB Output is correct
11 Correct 17 ms 35672 KB Output is correct
12 Correct 16 ms 35932 KB Output is correct
13 Correct 20 ms 35788 KB Output is correct
14 Correct 362 ms 53700 KB Output is correct
15 Correct 415 ms 55212 KB Output is correct
16 Correct 142 ms 45692 KB Output is correct
17 Correct 458 ms 51548 KB Output is correct
18 Correct 442 ms 51536 KB Output is correct
19 Correct 377 ms 55012 KB Output is correct
20 Correct 408 ms 54900 KB Output is correct
21 Correct 147 ms 49504 KB Output is correct
22 Correct 504 ms 59116 KB Output is correct
23 Correct 488 ms 59392 KB Output is correct
24 Correct 477 ms 59132 KB Output is correct
25 Correct 526 ms 59120 KB Output is correct
26 Correct 490 ms 52908 KB Output is correct
27 Correct 406 ms 52988 KB Output is correct
28 Correct 402 ms 56136 KB Output is correct
29 Correct 434 ms 56184 KB Output is correct
30 Correct 488 ms 62188 KB Output is correct
31 Correct 396 ms 62172 KB Output is correct
32 Correct 441 ms 59656 KB Output is correct
33 Correct 460 ms 59708 KB Output is correct
34 Correct 406 ms 52424 KB Output is correct
35 Correct 422 ms 53132 KB Output is correct
36 Correct 302 ms 49140 KB Output is correct
37 Correct 485 ms 56316 KB Output is correct
38 Correct 436 ms 58060 KB Output is correct
39 Correct 579 ms 59092 KB Output is correct
40 Correct 503 ms 57220 KB Output is correct
41 Correct 584 ms 59108 KB Output is correct
42 Correct 387 ms 52304 KB Output is correct
43 Correct 428 ms 52040 KB Output is correct
44 Correct 506 ms 56360 KB Output is correct
45 Correct 470 ms 55516 KB Output is correct
46 Correct 515 ms 58836 KB Output is correct
47 Correct 509 ms 54732 KB Output is correct
48 Correct 432 ms 58776 KB Output is correct
49 Correct 449 ms 54636 KB Output is correct
50 Correct 483 ms 59060 KB Output is correct
51 Correct 447 ms 53076 KB Output is correct
52 Correct 482 ms 56144 KB Output is correct
53 Correct 507 ms 62204 KB Output is correct
54 Correct 509 ms 59640 KB Output is correct
55 Correct 524 ms 59048 KB Output is correct
56 Correct 482 ms 54932 KB Output is correct
57 Correct 536 ms 51532 KB Output is correct
58 Correct 510 ms 51512 KB Output is correct
59 Correct 493 ms 57048 KB Output is correct
60 Correct 535 ms 54864 KB Output is correct
61 Correct 418 ms 62232 KB Output is correct
62 Correct 381 ms 62204 KB Output is correct
63 Correct 426 ms 59404 KB Output is correct
64 Correct 523 ms 54616 KB Output is correct