Submission #885940

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

apple

#include <bits/stdc++.h>

using namespace std;

struct node
{
    int sum, lazy;
    int nl, nr;
};

vector<node> aint;

void propagate(int nod, int st, int dr)
{
    if(aint[nod].lazy == 0)
        return;

    int mij = (st + dr) / 2;
    aint[aint[nod].nl].sum += (mij - st + 1) * aint[nod].lazy;
    aint[aint[nod].nr].sum += (dr - mij) * aint[nod].lazy;
    aint[aint[nod].nl].lazy = 1;
    aint[aint[nod].nr].lazy = 1;
    aint[nod].lazy = 0;
    return;
}

void update(int nod, int st, int dr, int le, int ri)
{
    if(le > ri)
        return;

    if(st == le && dr == ri)
    {
        aint[nod].sum = dr - st + 1;
        aint[nod].lazy = 1;
        return;
    }

    if(aint[nod].nl == -1)
    {
        aint[nod].nl = aint.size();
        aint.push_back({0, 0, -1, -1});
    }

    if(aint[nod].nr == -1)
    {
        aint[nod].nr = aint.size();
        aint.push_back({0, 0, -1, -1});
    }

    propagate(nod, st, dr);

    int mij = (st + dr) / 2;
    update(aint[nod].nl, st, mij, le, min(ri, mij));
    update(aint[nod].nr, mij + 1, dr, max(le, mij + 1), ri);
    aint[nod].sum = aint[aint[nod].nl].sum + aint[aint[nod].nr].sum;
}

int query(int nod, int st, int dr, int le, int ri)
{
    if(le > ri)
        return 0;
    if(st == le && dr == ri)
        return aint[nod].sum;

    if(aint[nod].nl == -1)
    {
        aint[nod].nl = aint.size();
        aint.push_back({0, 0, -1, -1});
    }

    if(aint[nod].nr == -1)
    {
        aint[nod].nr = aint.size();
        aint.push_back({0, 0, -1, -1});
    }

    propagate(nod, st, dr);
    int mij = (st + dr) / 2;
    return query(aint[nod].nl, st, mij, le, min(ri, mij)) +
           query(aint[nod].nr, mij + 1, dr, max(le, mij + 1), ri);
}

int main()
{
    aint.push_back({0, 0, -1, -1});
    int m, c = 0;
    cin>>m;
    for(int i = 1; i <= m; i++)
    {
        int t, x, y;
        cin>>t>>x>>y;
        x += c;
        y += c;

        if(t == 1)
        {
            int rez = query(0, 1, 1e9, x, y);
            cout<<rez<<'\n';
            c = rez;
        }
        else
        {
            update(0, 1, 1e9, x, y);
        }
    }
    return 0;
}

• Subtask 1: 0 / 100