Submission #1103737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103737		cpismylifeOwO	Fish 3 (JOI24_fish3)	C++17	100 / 100	830 ms	59828 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

struct Query
{
    int l, r, id;

    bool operator < (const Query& other) const
    {
        return this->r < other.r;
    }
};

int n, q;
long long d;
long long arr[MaxN];
Query query[MaxN];

void Inp()
{
    cin >> n >> d;
    for (int x = 1; x <= n; x++)
    {
        cin >> arr[x];
    }
    cin >> q;
    for (int x = 1; x <= q; x++)
    {
        cin >> query[x].l >> query[x].r;
        query[x].id = x;
    }
    sort(query + 1, query + q + 1);
}

int parents[MaxN];
int sz[MaxN];
int mx[MaxN];
int mi[MaxN];

int FindSet(int p)
{
    if (parents[p] == p)
    {
        return p;
    }
    parents[p] = FindSet(parents[p]);
    return parents[p];
}

void UnionSet(int a, int b)
{
    a = FindSet(a);
    b = FindSet(b);
    if (a == b)
    {
        return;
    }
    if (sz[a] < sz[b])
    {
        swap(a, b);
    }
    parents[b] = a;
    sz[a] += sz[b];
    mx[a] = max(mx[a], mx[b]);
    mi[a] = min(mi[a], mi[b]);
}

long long SegTree[4 * MaxN];
long long SegTree2[4 * MaxN];
long long Lazy[4 * MaxN];

void Fix(int id, int l, int r)
{
    if (Lazy[id] == 0)
    {
        return;
    }
    SegTree[id] += Lazy[id] * (r - l + 1);
    SegTree2[id] -= Lazy[id] * d;
    if (l != r)
    {
        Lazy[id << 1] += Lazy[id];
        Lazy[id << 1 | 1] += Lazy[id];
    }
    Lazy[id] = 0;
}

void Build(int id, int l, int r)
{
    Lazy[id] = 0;
    if (l == r)
    {
        SegTree2[id] = arr[l];
        return;
    }
    int mid = (l + r) >> 1;
    Build(id << 1, l, mid);
    Build(id << 1 | 1, mid + 1, r);
    SegTree2[id] = min(SegTree2[id << 1], SegTree2[id << 1 | 1]);
}

void Update(int id, int l, int r, int i, int j, long long v)
{
    Fix(id, l, r);
    if (j < l || r < i)
    {
        return;
    }
    if (i <= l && r <= j)
    {
        Lazy[id] += v;
        Fix(id, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    Update(id << 1, l, mid, i, j, v);
    Update(id << 1 | 1, mid + 1, r, i, j, v);
    SegTree[id] = SegTree[id << 1] + SegTree[id << 1 | 1];
    SegTree2[id] = min(SegTree2[id << 1], SegTree2[id << 1 | 1]);
}

long long Get1(int id, int l, int r, int i, int j)
{
    Fix(id, l, r);
    if (j < l || r < i)
    {
        return 0;
    }
    if (i <= l && r <= j)
    {
        return SegTree[id];
    }
    int mid = (l + r) >> 1;
    return Get1(id << 1, l, mid, i, j) + Get1(id << 1 | 1, mid + 1, r, i, j);
}

long long Get2(int id, int l, int r, int i, int j)
{
    Fix(id, l, r);
    if (j < l || r < i)
    {
        return 1e18;
    }
    if (i <= l && r <= j)
    {
        return SegTree2[id];
    }
    int mid = (l + r) >> 1;
    return min(Get2(id << 1, l, mid, i, j), Get2(id << 1 | 1, mid + 1, r, i, j));
}

long long res[MaxN];

void Exc()
{
    for (int x = 1; x <= n; x++)
    {
        parents[x] = x;
        sz[x] = 1;
        mi[x] = x;
        mx[x] = x;
    }
    for (int x = 1; x <= q; x++)
    {
        res[x] = -1;
    }
    Build(1, 1, n);
    int y = 1;
    for (int x = 1; x <= n; x++)
    {
        int p = x;
        while (p > 1 && Get2(1, 1, n, p - 1, p - 1) > Get2(1, 1, n, p, p))
        {
            int t = FindSet(p - 1);
            long long k = Get2(1, 1, n, p - 1, p - 1) - Get2(1, 1, n, p, p);
            //if (x == 2) cout << p - 1 << " ";
            k = (k + d - 1) / d;
            Update(1, 1, n, mi[t], mx[t], k);
            UnionSet(p - 1, p);
            p = mi[FindSet(p)];
        }
        while (y <= q && query[y].r == x)
        {
            if (Get2(1, 1, n, query[y].l, query[y].r) >= 0)
            {
                res[query[y].id] = Get1(1, 1, n, query[y].l, query[y].r);
            }
            y++;
        }
    }
    for (int x = 1; x <= q; x++)
    {
        cout << res[x] << "\n";
    }
}

int main()
{
    //freopen("A.INP", "r", stdin);
    //freopen("A.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 7 / 7
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36