oj.uz

Submission #1103737

# Submission time Handle Problem Language Result Execution time Memory
1103737 2024-10-21T15:31:09 Z cpismylifeOwO Fish 3 (JOI24_fish3) C++17
100 / 100
 830 ms 59828 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16720 KB Output is correct
2 Correct 3 ms 16720 KB Output is correct
3 Correct 3 ms 18768 KB Output is correct
4 Correct 8 ms 20816 KB Output is correct
5 Correct 7 ms 20816 KB Output is correct
6 Correct 7 ms 20816 KB Output is correct
7 Correct 6 ms 20816 KB Output is correct
8 Correct 6 ms 20816 KB Output is correct
9 Correct 7 ms 20816 KB Output is correct
10 Correct 7 ms 20988 KB Output is correct
11 Correct 6 ms 21016 KB Output is correct
12 Correct 5 ms 18768 KB Output is correct
13 Correct 5 ms 18784 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 56280 KB Output is correct
2 Correct 517 ms 48968 KB Output is correct
3 Correct 123 ms 27976 KB Output is correct
4 Correct 594 ms 56904 KB Output is correct
5 Correct 607 ms 56904 KB Output is correct
6 Correct 515 ms 50504 KB Output is correct
7 Correct 529 ms 50440 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 29912 KB Output is correct
2 Correct 750 ms 59720 KB Output is correct
3 Correct 729 ms 59608 KB Output is correct
4 Correct 742 ms 59600 KB Output is correct
5 Correct 824 ms 59828 KB Output is correct
6 Correct 721 ms 56540 KB Output is correct
7 Correct 736 ms 56740 KB Output is correct
8 Correct 786 ms 56540 KB Output is correct
9 Correct 798 ms 58076 KB Output is correct
10 Correct 490 ms 46152 KB Output is correct
11 Correct 483 ms 46292 KB Output is correct
12 Correct 638 ms 58076 KB Output is correct
13 Correct 606 ms 58072 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 39068 KB Output is correct
2 Correct 662 ms 55112 KB Output is correct
3 Correct 350 ms 32664 KB Output is correct
4 Correct 735 ms 55088 KB Output is correct
5 Correct 604 ms 57420 KB Output is correct
6 Correct 643 ms 59492 KB Output is correct
7 Correct 572 ms 44496 KB Output is correct
8 Correct 675 ms 59612 KB Output is correct
9 Correct 650 ms 54344 KB Output is correct
10 Correct 632 ms 54088 KB Output is correct
11 Correct 830 ms 55116 KB Output is correct
12 Correct 679 ms 54408 KB Output is correct
13 Correct 593 ms 59464 KB Output is correct
14 Correct 497 ms 56904 KB Output is correct
15 Correct 607 ms 59208 KB Output is correct
16 Correct 492 ms 56788 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16720 KB Output is correct
2 Correct 3 ms 16720 KB Output is correct
3 Correct 3 ms 18768 KB Output is correct
4 Correct 8 ms 20816 KB Output is correct
5 Correct 7 ms 20816 KB Output is correct
6 Correct 7 ms 20816 KB Output is correct
7 Correct 6 ms 20816 KB Output is correct
8 Correct 6 ms 20816 KB Output is correct
9 Correct 7 ms 20816 KB Output is correct
10 Correct 7 ms 20988 KB Output is correct
11 Correct 6 ms 21016 KB Output is correct
12 Correct 5 ms 18768 KB Output is correct
13 Correct 5 ms 18784 KB Output is correct
14 Correct 598 ms 56280 KB Output is correct
15 Correct 517 ms 48968 KB Output is correct
16 Correct 123 ms 27976 KB Output is correct
17 Correct 594 ms 56904 KB Output is correct
18 Correct 607 ms 56904 KB Output is correct
19 Correct 515 ms 50504 KB Output is correct
20 Correct 529 ms 50440 KB Output is correct
21 Correct 172 ms 29912 KB Output is correct
22 Correct 750 ms 59720 KB Output is correct
23 Correct 729 ms 59608 KB Output is correct
24 Correct 742 ms 59600 KB Output is correct
25 Correct 824 ms 59828 KB Output is correct
26 Correct 721 ms 56540 KB Output is correct
27 Correct 736 ms 56740 KB Output is correct
28 Correct 786 ms 56540 KB Output is correct
29 Correct 798 ms 58076 KB Output is correct
30 Correct 490 ms 46152 KB Output is correct
31 Correct 483 ms 46292 KB Output is correct
32 Correct 638 ms 58076 KB Output is correct
33 Correct 606 ms 58072 KB Output is correct
34 Correct 590 ms 39068 KB Output is correct
35 Correct 662 ms 55112 KB Output is correct
36 Correct 350 ms 32664 KB Output is correct
37 Correct 735 ms 55088 KB Output is correct
38 Correct 604 ms 57420 KB Output is correct
39 Correct 643 ms 59492 KB Output is correct
40 Correct 572 ms 44496 KB Output is correct
41 Correct 675 ms 59612 KB Output is correct
42 Correct 650 ms 54344 KB Output is correct
43 Correct 632 ms 54088 KB Output is correct
44 Correct 830 ms 55116 KB Output is correct
45 Correct 679 ms 54408 KB Output is correct
46 Correct 593 ms 59464 KB Output is correct
47 Correct 497 ms 56904 KB Output is correct
48 Correct 607 ms 59208 KB Output is correct
49 Correct 492 ms 56788 KB Output is correct
50 Correct 793 ms 59760 KB Output is correct
51 Correct 745 ms 56356 KB Output is correct
52 Correct 732 ms 56536 KB Output is correct
53 Correct 471 ms 46300 KB Output is correct
54 Correct 659 ms 58072 KB Output is correct
55 Correct 783 ms 59608 KB Output is correct
56 Correct 590 ms 56904 KB Output is correct
57 Correct 599 ms 56796 KB Output is correct
58 Correct 570 ms 56792 KB Output is correct
59 Correct 680 ms 59100 KB Output is correct
60 Correct 548 ms 56792 KB Output is correct
61 Correct 427 ms 46152 KB Output is correct
62 Correct 417 ms 46152 KB Output is correct
63 Correct 693 ms 57808 KB Output is correct
64 Correct 564 ms 56792 KB Output is correct