Submission #870943

#	Time	Username	Problem	Language	Result	Execution time	Memory
870943		12345678	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	249 ms	166968 KiB

apple

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e9+5;
ll m, t, x, y, c;

struct segtree
{
    struct node
    {
        ll vl, lz;
        node *l, *r;
        node(): vl(0), lz(0), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt;
    void pushlz(int l, int r, pnode x)
    {
        if (x->lz==0) return;
        x->vl=r-l+1;
        x->lz=0;
        if (l==r) return;
        if (!(x->l)) x->l=new node();
        x->l->lz=1;
        if (!(x->r)) x->r=new node();
        x->r->lz=1;
    }
    void update(int l, int r, pnode &x, int ql, int qr)
    {
        if (r<ql||qr<l) return;
        if (x&&x->vl==r-l+1) return;
        if (!x) x=new node();
        pushlz(l, r, x);
        if (ql<=l&&r<=qr) return x->lz=1, pushlz(l, r, x), void();
        int md=(l+r)/2;
        update(l, md, x->l, ql, qr);
        update(md+1, r, x->r, ql, qr);
        x->vl=((x->l)?(x->l->vl):0)+((x->r)?(x->r->vl):0);
    }
    ll query(int l, int r, pnode x, int ql, int qr)
    {
        if (r<ql||qr<l||!x) return 0;
        pushlz(l, r, x);
        if (ql<=l&&r<=qr) return x->vl;
        int md=(l+r)/2;
        return query(l, md, x->l, ql, qr)+query(md+1, r, x->r, ql, qr);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>m;
    while (m--)
    {
        cin>>t>>x>>y;
        x+=c; y+=c;
        if (t==1) 
        {
            ll res=s.query(1, nx, s.rt, x, y);
            c=res;
            cout<<res<<'\n';
        }
        else s.update(1, nx, s.rt, x, y);
    }
}

• Subtask 1: 100 / 100