Submission #1271882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271882		nerrrmin	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	0 ms	328 KiB

apple

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const long long maxn = 1e6 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
struct sparse_sgt
{
    struct node
    {
        long long lt, rt, val, lazy;
        node()
        {
            lt = -1;
            rt = -1;
            val = 0;
            lazy = 0;
        };
        node(long long _lt, long long _rt, long long _val, long long _lazy)
        {
            lt = _lt;
            rt = _rt;
            val = _val;
            lazy = _lazy;
        }
    };
    long long n, tmr;
    vector < node > t;
    void init(long long sz)
    {
        n = sz;
        t.pb(node(-1, -1, 0, 0));
        tmr = 1;
    }
    void push_lazy(long long i, long long l, long long r)
    {
        long long curr = t[i].lazy;
        if(curr == 0)return;
        if(l != r)
        {
            if(t[i].lt == -1)
            {
                t.pb(node(-1, -1, 0, 0));
                t[i].lt = tmr;
                tmr ++;
            }
            if(t[i].rt == -1)
            {
                t.pb(node(-1, -1, 0, 0));
                t[i].rt = tmr;
                tmr ++;
            }
            t[t[i].lt].lazy += curr;
            t[t[i].rt].lazy += curr;
        }
        t[i].val += t[i].lazy * (r - l + 1);
        t[i].lazy = 0;
    }
    long long query(long long i, long long l, long long r, long long ql, long long qr)
    {
        push_lazy(i, l, r);
        if(qr < l || ql > r)return 0;
        if(ql <= l && r <= qr)
        {
            return t[i].val;
        }
        long long mid = (l + r)/2;
        long long onleft = t[i].lt, ansleft = 0;
        if(onleft != -1)ansleft = query(onleft, l, mid, ql, qr);
        long long onright = t[i].rt, ansright = 0;
        if(onright != -1)ansright = query(onright, mid+1, r, ql, qr);
        return ansleft + ansright;
    }
    void update(long long i, long long l, long long r, long long ql, long long qr, long long upd_val)
    {
        //cout << i << " " << l << " " << r << endl;

        push_lazy(i, l, r);
        if(qr < l || ql > r)return;
        if(ql <= l && r <= qr)
        {
            t[i].lazy += upd_val;
            push_lazy(i, l, r);
            return;
        }
        long long mid = (l + r)/2;
        if(t[i].lt == -1)
        {
            t[i].lt = tmr;
            t.pb(node(-1, -1, 0, 0));
            tmr ++;
        }
        if(t[i].rt == -1)
        {
            t[i].rt = tmr;
            t.pb(node(-1, -1, 0, 0));
            tmr ++;
        }
        //cout << t[i].lt << " , " << t[i].rt << endl;
        update(t[i].lt, l, mid, ql, qr, upd_val);
        update(t[i].rt, mid+1, r, ql, qr, upd_val);
        t[i].val = t[t[i].lt].val + t[t[i].rt].val;
    }
    void do_update(long long ql, long long qr, long long upd_val)
    {
        update(0, 1, 1e9, ql, qr, upd_val);
    }
    long long do_query(long long ql, long long qr)
    {
        return query(0, 1, 1e9, ql, qr);
    }
};
sparse_sgt s;
int main()
{
    speed();
    long long q;
    cin >> q;
    s.init(1e9);
    long long c = 0;
    while(q --)
    {
        long long t, x, y;
        cin >> t >> x >> y;
        if(t == 1)
        {
            long long curr = s.do_query(x + c, y + c);
            c = curr;
            cout << curr << endl;
        }
        else
        {
            s.do_update(x + c, y + c, 1);
        }
    }
    return 0;
}

• Subtask 1: 0 / 100