Submission #986501

#	Time	Username	Problem	Language	Result	Execution time	Memory
986501		boris_mihov	Fish 3 (JOI24_fish3)	C++17	100 / 100	584 ms	62232 KiB

Main

#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 (stderr)

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 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36