답안 #797008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797008 2023-07-29T04:06:39 Z normankr07 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
280 ms 139468 KB
#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) {}
      |         ^~~~~
# 결과 실행 시간 메모리 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