Submission #873775

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

apple

#include <iostream>

using namespace std;

const int NMAX = 1e9;

struct node
{
    node *lft, *rgt;
    bool lazy;
    int ans;

    node()
    {
        lft = rgt = NULL;
        lazy = 0;
        ans = 0;
    }
};

void create(node *nod, bool ok)
{
    if (ok == 0)
    {
        if (nod->lft == NULL)
            nod->lft = new node();
    }
    else
    {
        if (nod->rgt == NULL)
            nod->rgt = new node();
    }
}

void propag(node *nod, int st, int dr)
{
    create(nod, 0);
    create(nod, 1);
    if (nod->lazy == true)
    {
        nod->ans = dr - st + 1;
        if (st != dr)
        {
            nod->lft->lazy = 1;
            nod->rgt->lazy = 1;
        }
    }
    nod->lazy = 0;
}

void update(node *nod, int st, int dr, int a, int b)
{
    propag(nod, st, dr);
    if (dr < a or st > b)
        return ;
    if (a <= st and dr <= b)
    {
        nod->lazy = 1;
        propag(nod, st, dr);
        return ;
    }
    int med = ((st + dr) >> 1);
    update(nod->lft, st, med, a, b);
    update(nod->rgt, med + 1, dr, a, b);
    nod->ans = nod->lft->ans + nod->rgt->ans;
}

int query(node *nod, int st, int dr, int a, int b)
{
    propag(nod, st, dr);
    if (dr < a or st > b)
        return 0;
    if (a <= st and dr <= b)
    {
        return nod->ans;
    }
    int med = ((st + dr) >> 1);
    int v1 = query(nod->lft, st, med, a, b);
    int v2 = query(nod->rgt, med + 1, dr, a, b);
    return v1 + v2;
}


int main()
{
 //  ifstream cin("f.in");
//ofstream cout("f.out");
    int n;
    cin >> n;
    int ans = 0;
    node *nod = new node();
    while (n--)
    {
        int op, a, b;
        cin >> op >> a >> b;
            a += ans;
            b += ans;
        if (op == 1)
        {
            int val = query(nod, 1, NMAX, a, b);
            cout << val << "\n";
            ans = val;
        }
        else
            update(nod, 1, NMAX, a, b);
    }
    return 0;
}

• Subtask 1: 0 / 100