Submission #531254

#	Time	Username	Problem	Language	Result	Execution time	Memory
531254		dreadarceus	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	40 ms	33124 KiB

apple

// Lazy no dynamic
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct SegTreeItem
{
    int element;
};

class LazySegTree
{
  public:
    LazySegTree(int n)
    {
        this->nodes.resize(4 * n + 5, this->null);
        this->pendingLazy.resize(4 * n + 5, false);
        this->size = n;
    }
    void pointUpdate(int x, SegTreeItem val, int index, int l, int r)
    {
        if (pendingLazy[index])
            propagateLazy(index, l, r);
        if (x < l || x >= r)
            return;
        if (l == x && r == x + 1)
        {
            nodes[index] = val;
            return;
        }
        pointUpdate(x, val, 2 * index, l, (r + l) / 2);
        pointUpdate(x, val, 2 * index + 1, (r + l) / 2, r);
        nodes[index] = merge(nodes[2 * index], nodes[2 * index + 1]);
    }
    void rangeUpdate(int x, int y, int index, int l, int r)
    {
        if (pendingLazy[index])
            propagateLazy(index, l, r);
        if (y <= l || x >= r)
            return;
        if (l >= x && r <= y)
        {
            pendingLazy[index] = true;
            propagateLazy(index, l, r);
            return;
        }
        rangeUpdate(x, y, 2 * index, l, (r + l) / 2);
        rangeUpdate(x, y, 2 * index + 1, (r + l) / 2, r);
        nodes[index] = merge(nodes[2 * index], nodes[2 * index + 1]);
    }
    SegTreeItem query(int x, int y, int index, int l, int r)
    {
        if (pendingLazy[index])
            propagateLazy(index, l, r);
        if (y <= l || x >= r)
            return this->null;
        if (l >= x && r <= y)
            return nodes[index];
        return merge(query(x, y, 2 * index, l, (r + l) / 2), query(x, y, 2 * index + 1, (r + l) / 2, r));
    }
    void pointUpdate(int x, SegTreeItem val)
    {
        pointUpdate(x, val, 1, 0, size);
    }
    void pointUpdate(int x, int val)
    {
        pointUpdate(x, {val}, 1, 0, size);
    }
    void rangeUpdate(int x, int y)
    {
        rangeUpdate(x, y, 1, 0, size);
    }
    SegTreeItem query(int x, int y)
    {
        return query(x, y, 1, 0, size);
    }

  private:
    vector<SegTreeItem> nodes;
    vector<bool> pendingLazy;
    SegTreeItem null = {0};
    int size;
    void propagateLazy(int index, int l, int r)
    {
        if (l != r - 1)
        {
            pendingLazy[2 * index] = true;
            pendingLazy[2 * index + 1] = true;
        }
        nodes[index].element = r - l;
        pendingLazy[index] = false;
    }
    SegTreeItem merge(SegTreeItem a, SegTreeItem b)
    {
        SegTreeItem result;
        result.element = a.element + b.element;
        return result;
    }
};

void solveCase()
{
    int m = 0;
    cin >> m;

    LazySegTree lst(1000001);

    int c = 0;
    while (m--)
    {
        int d = 0, x = 0, y = 0;
        cin >> d >> x >> y;
        if (d == 1)
        {
            c = lst.query(x + c, y + c + 1).element;
            cout << c << '\n';
        }
        else
        {
            lst.rangeUpdate(x + c, y + c + 1);
        }
    }
}

int32_t main()
{
    mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());
    if (rng() % 100000 == 0)
        assert(false);

    ios::sync_with_stdio(false), cin.tie(NULL);
    solveCase();
}

• Subtask 1: 0 / 100