Submission #797011

#TimeUsernameProblemLanguageResultExecution timeMemory
797011normankr07원숭이와 사과 나무 (IZhO12_apple)C++17
100 / 100
275 ms133964 KiB
#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) {}
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...