Submission #870943

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870943	2023-11-09T14:33:58 Z	12345678	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	249 ms	166968 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	600 KB	Output is correct
4	Correct	7 ms	4308 KB	Output is correct
5	Correct	9 ms	5324 KB	Output is correct
6	Correct	9 ms	4956 KB	Output is correct
7	Correct	9 ms	5084 KB	Output is correct
8	Correct	69 ms	38496 KB	Output is correct
9	Correct	131 ms	67152 KB	Output is correct
10	Correct	161 ms	73300 KB	Output is correct
11	Correct	139 ms	78420 KB	Output is correct
12	Correct	143 ms	80468 KB	Output is correct
13	Correct	134 ms	89080 KB	Output is correct
14	Correct	151 ms	88696 KB	Output is correct
15	Correct	222 ms	161932 KB	Output is correct
16	Correct	216 ms	163156 KB	Output is correct
17	Correct	139 ms	91196 KB	Output is correct
18	Correct	143 ms	91676 KB	Output is correct
19	Correct	229 ms	166740 KB	Output is correct
20	Correct	249 ms	166968 KB	Output is correct