Submission #797011

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
797011	2023-07-29T04:13:29 Z	normankr07	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	275 ms	133964 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;
    }

    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

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.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	0 ms	212 KB	Output is correct
4	Correct	9 ms	3156 KB	Output is correct
5	Correct	11 ms	3796 KB	Output is correct
6	Correct	10 ms	3668 KB	Output is correct
7	Correct	12 ms	3864 KB	Output is correct
8	Correct	83 ms	28120 KB	Output is correct
9	Correct	166 ms	50164 KB	Output is correct
10	Correct	164 ms	53628 KB	Output is correct
11	Correct	169 ms	57740 KB	Output is correct
12	Correct	187 ms	59612 KB	Output is correct
13	Correct	166 ms	70532 KB	Output is correct
14	Correct	166 ms	71144 KB	Output is correct
15	Correct	266 ms	129956 KB	Output is correct
16	Correct	266 ms	130792 KB	Output is correct
17	Correct	170 ms	73676 KB	Output is correct
18	Correct	192 ms	73752 KB	Output is correct
19	Correct	275 ms	133836 KB	Output is correct
20	Correct	265 ms	133964 KB	Output is correct