Submission #788415

#	Time	Username	Problem	Language	Result	Execution time	Memory
788415		normankr07	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	212 KiB

apple

// I didnt use templete istg
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Range add, range sum query Dynamic ST
// Based on : https://nyaannyaan.github.io/library/segment-tree/dynamic-segment-tree.hpp
struct DynamicST
{
    struct TNode;
    using PNode = TNode *;
    struct TNode
    {
        ll val, lazy;
        PNode l, r;
        TNode() : l(NULL), r(NULL), val(0), lazy(0) {}
    };

    PNode root;
    ll nodecnt;

    PNode newnode()
    {
        return new TNode();
    }
    void delnode(PNode p)
    {
        delete p;
    }

    DynamicST(ll n = 0)
    {
        nodecnt = 2;
        while (nodecnt <= n)
            nodecnt *= 2;
        root = newnode();
    }

    void downtree(PNode v, int l, int r)
    {
        if (v->lazy != -1)
        {
            if (v->l == NULL)
                v->l = newnode();
            if (v->r == NULL)
                v->r = newnode();
            int len = r - l + 1;
            v->l->val = (len - len / 2) * v->lazy;
            v->l->lazy = v->r->lazy = v->lazy;
            v->lazy = -1;
        }
    }

    void update(PNode v, int tl, int tr, int l, int r)
    {
        if (l <= tl && tr <= r)
        {
            v->val = tr - tl + 1;
            v->lazy = 1;
        }
        else if (l <= tr && tl <= r)
        {
            downtree(v, tl, tr);
            int tm = (tl + tr) >> 1;
            update(v->l, tl, tm, l, r);
            update(v->r, tm + 1, tr, l, r);
            v->val = v->l->val + v->r->val;
        }
    }

    ll query(PNode v, int tl, int tr, int l, int r)
    {
        if (l <= tl && tr <= r)
        {
            return v->val;
        }
        else if (l <= tr && tl <= r)
        {
            downtree(v, tl, tr);
            int tm = (tl + tr) >> 1;
            ll q1 = query(v->l, tl, tm, l, r);
            ll q2 = query(v->r, tm + 1, tr, l, r);
            return q1 + q2;
        }
        return 0;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // freopen("task.inp", "r", stdin);
    // freopen("task.out", "w", stdout);
    int q;
    cin >> q;
    int pre = 0;
    DynamicST f;
    while (q--)
    {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1)
        {
            ll ans = f.query(f.root, INT_MIN, INT_MAX, l, r);
            pre = ans;
            cout << ans << '\n';
        }
        else
        {
            f.update(f.root, INT_MIN, INT_MAX, l + pre, r + pre);
        }
    }
}

Compilation message (stderr)

apple.cpp: In constructor 'DynamicST::TNode::TNode()':
apple.cpp:15:18: warning: 'DynamicST::TNode::r' will be initialized after [-Wreorder]
   15 |         PNode l, r;
      |                  ^
apple.cpp:14:12: warning:   'll DynamicST::TNode::val' [-Wreorder]
   14 |         ll val, lazy;
      |            ^~~
apple.cpp:16:9: warning:   when initialized here [-Wreorder]
   16 |         TNode() : l(NULL), r(NULL), val(0), lazy(0) {}
      |         ^~~~~

• Subtask 1: 0 / 100