Submission #797008

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
797008	2023-07-29T04:06:39 Z	normankr07	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	280 ms	139468 KB

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;
    }
};

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(f.root, 1, 1e9, u, v);
            cout << pre << '\n';
        }
        else
            f.update(f.root, 1, 1e9, u, v, 1);
    }
}

Compilation message

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	9 ms	3424 KB	Output is correct
5	Correct	11 ms	4092 KB	Output is correct
6	Correct	14 ms	4020 KB	Output is correct
7	Correct	14 ms	4180 KB	Output is correct
8	Correct	78 ms	30072 KB	Output is correct
9	Correct	163 ms	52324 KB	Output is correct
10	Correct	183 ms	57668 KB	Output is correct
11	Correct	198 ms	61900 KB	Output is correct
12	Correct	207 ms	63844 KB	Output is correct
13	Correct	173 ms	74324 KB	Output is correct
14	Correct	168 ms	74936 KB	Output is correct
15	Correct	273 ms	135484 KB	Output is correct
16	Correct	280 ms	136416 KB	Output is correct
17	Correct	177 ms	77428 KB	Output is correct
18	Correct	173 ms	77480 KB	Output is correct
19	Correct	277 ms	139468 KB	Output is correct
20	Correct	272 ms	139420 KB	Output is correct