Submission #1182367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182367		SteveBro	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	147 ms	75548 KiB

apple

#include <bits/stdc++.h>
#define inf 1e9
using namespace std;
const int nmax = 1e9;
class SegmentTree
{
public:
    SegmentTree *lnod, *rnod;
    int val;
    bool lazy;
    SegmentTree()
    {
        lazy = false;
        val = 0;
        lnod = rnod = NULL;
    }
}*root;
void pull(SegmentTree *nod)
{
    nod -> val = 0;
    if(nod -> lnod != NULL)
        nod -> val += nod -> lnod -> val;
    if(nod -> rnod != NULL)
        nod -> val += nod -> rnod -> val;
}
void push(SegmentTree *nod, int st, int dr)
{
    if(!(nod -> lazy))
        return;
    nod -> lazy = 0;
    int mij = (st + dr) / 2;
    if(nod -> lnod == NULL)
        nod -> lnod = new SegmentTree();
    if(nod -> rnod == NULL)
        nod -> rnod = new SegmentTree();
    nod -> lnod -> lazy = 1;
    nod -> lnod -> val = mij - st + 1;
    nod -> rnod -> lazy = 1;
    nod -> rnod -> val = dr - mij;
}
void upd(SegmentTree *nod, int st, int dr, int l, int r)
{
    if(nod -> lazy)
        return;
    if(l <= st && dr <= r)
    {
        nod -> lazy = 1;
        nod -> val = dr - st + 1;
        return;
    }
    int mij = (st + dr) / 2;
    if(l <= mij)
    {
        if(nod -> lnod == NULL)
            nod -> lnod = new SegmentTree();
        upd(nod -> lnod, st, mij, l, r);
    }
    if(r > mij)
    {
        if(nod -> rnod == NULL)
            nod -> rnod = new SegmentTree();
        upd(nod -> rnod, mij + 1, dr, l, r);
    }
    pull(nod);
}
void qry(SegmentTree *nod, int st, int dr, int l, int r, int &rez)
{
    if(l <= st && dr <= r)
    {
        rez += nod -> val;
        return;
    }
    push(nod, st, dr);
    int mij = (st + dr) / 2;
    if(l <= mij)
    {
        if(nod -> lnod != NULL)
            qry(nod -> lnod, st, mij, l, r, rez);
    }
    if(r > mij)
    {
        if(nod -> rnod != NULL)
            qry(nod -> rnod, mij + 1, dr, l, r, rez);
    }
    pull(nod);
}
int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0);
    ///freopen("f.in", "r", stdin);
    ///freopen("f.out", "w", stdout);
    root = new SegmentTree();
    int m, t, x, y, c = 0, n;
    n = nmax;
    cin >> m;
    while(m > 0)
    {
        m--;
        cin >> t >> x >> y;
        x += c;
        y += c;
        if(t == 2) /// upd
        {
            upd(root, 1, n, x, y);
        }
        else /// qry
        {
            c = 0;
            qry(root, 1, n, x, y, c);
            cout << c << '\n';
        }
    }
    return 0;
}

• Subtask 1: 100 / 100