Submission #719332

#	Time	Username	Problem	Language	Result	Execution time	Memory
719332		Muaath_5	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	387 ms	262144 KiB

apple

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e9+10;

struct segnode {
    int sum = 0;
    int upd = 0;
    int s, e;
    segnode *segleft, *segright;
    segnode() : s(1), e(N), segleft(nullptr), segright(nullptr) {}
    segnode(int s, int e) : s(s), e(e), segleft(nullptr), segright(nullptr) {}
};

segnode* root;

void pushdown(segnode* node)
{
    if (node->upd != 1) return;

    const int mid = (node->s + node->e) / 2;

    if (!node->segleft && node->s < node->e)
        node->segleft = new segnode(node->s, mid);
    if (node->s < node->e)
        node->segleft->upd = 1;

    if (!node->segright && node->s < node->e)
        node->segright = new segnode(mid + 1, node->e);
    if (node->s < node->e)
        node->segright->upd = 1;
    node->upd = 2;
    node->sum = (node->e - node->s + 1);
}

void lazy_update(segnode* node, int l, int r) {
    pushdown(node);
    if (node->e < l || node->s > r) return;
    if (l <= node->s && node->e <= r) {
        node->upd = max(node->upd, 1);
        pushdown(node);
        return;
    }
    const int mid = (node->s + node->e) / 2;

    if (!node->segleft && node->s < node->e)
        node->segleft = new segnode(node->s, mid);
    if (!node->segright && node->s < node->e)
        node->segright = new segnode(mid+1, node->e);

    int cur = 0;
    if (node->segleft) {
        lazy_update(node->segleft, l, r);
        cur += node->segleft->sum;
    }
    if (node->segright) {
        lazy_update(node->segright, l, r);
        cur += node->segright->sum;
    }
    node->sum = cur;
}

int query(segnode* node, int l, int r) {
    pushdown(node);
    if (node->e < l || node->s > r) return 0;
    if (l <= node->s && node->e <= r)
        return node->sum;
    int sum = 0;
    if (node->segleft)
        sum += query(node->segleft, l, r);
    if (node->segright)
        sum += query(node->segright, l, r);
    return sum;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int q, cmd, x, y;
    cin >> q;
    root = new segnode();
    int c = 0;
    while (q--) {
        cin >> cmd >> x >> y;
        if (cmd == 1) {
            c = query(root, x+c, y+c);
            cout << c << '\n';
        }
        else if (cmd == 2) {
            lazy_update(root, x+c, y+c);
        }
    }
}

• Subtask 1: 0 / 100