Submission #797011

#	Time	Username	Problem	Language	Result	Execution time	Memory
797011		normankr07	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	275 ms	133964 KiB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int q;

template <typename T = int>
struct DynamicST
{
    struct TNode;
    using PNode = TNode *;

    struct TNode
    {
        T val, lazy;
        PNode l, r;
        TNode() : l(NULL), r(NULL), val(0), lazy(0) {}
    };

    PNode root;

    DynamicST()
    {
        root = new TNode();
    }

    void downtree(PNode v, int tl, int tr)
    {
        if (v->lazy == 0)
            return;
        if (v->l == NULL)
            v->l = new TNode();
        if (v->r == NULL)
            v->r = new TNode();

        int tm = (tl + tr) >> 1;
        v->l->lazy = v->lazy;
        v->l->val = v->lazy * (tm - tl + 1);
        v->r->lazy = v->lazy;
        v->r->val = v->lazy * (tr - tm);
    }

    T query(PNode v, int tl, int tr, int l, int r)
    {
        if (tl > r || tr < l)
            return 0;
        if (l <= tl && tr <= r)
            return v->val;
        if (v->l == NULL)
            v->l = new TNode();
        if (v->r == NULL)
            v->r = new TNode();
        downtree(v, tl, tr);
        int tm = (tl + tr) >> 1;
        return query(v->l, tl, tm, l, r) + query(v->r, tm + 1, tr, l, r);
    }

    void update(PNode v, int tl, int tr, int l, int r, int add)
    {
        if (tl > r || tr < l)
            return;
        if (l <= tl && tr <= r)
        {
            // Assign query
            v->val = add * (tr - tl + 1);
            v->lazy = add;
            return;
        }
        if (v->l == NULL)
            v->l = new TNode();
        if (v->r == NULL)
            v->r = new TNode();
        downtree(v, tl, tr);
        int tm = (tl + tr) >> 1;
        update(v->l, tl, tm, l, r, add);
        update(v->r, tm + 1, tr, l, r, add);
        v->val = v->l->val + v->r->val;
    }

    T query(int l, int r)
    {
        return query(root, 1, std::numeric_limits<T>::max() - 1, l, r);
    }

    void update(int l, int r, T val)
    {
        update(root, 1, std::numeric_limits<T>::max() - 1, l, r, val);
    }
};

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

Compilation message (stderr)

apple.cpp: In instantiation of 'DynamicST<T>::TNode::TNode() [with T = int]':
apple.cpp:24:16:   required from 'DynamicST<T>::DynamicST() [with T = int]'
apple.cpp:99:17:   required from here
apple.cpp:16:18: warning: 'DynamicST<>::TNode::r' will be initialized after [-Wreorder]
   16 |         PNode l, r;
      |                  ^
apple.cpp:15:11: warning:   'int DynamicST<>::TNode::val' [-Wreorder]
   15 |         T val, lazy;
      |           ^~~
apple.cpp:17:9: warning:   when initialized here [-Wreorder]
   17 |         TNode() : l(NULL), r(NULL), val(0), lazy(0) {}
      |         ^~~~~

• Subtask 1: 100 / 100