제출 #1271893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271893		nerrrmin	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	273 ms	132292 KiB

apple

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