Submission #228784

#TimeUsernameProblemLanguageResultExecution timeMemory
228784Haunted_CppMonkey and Apple-trees (IZhO12_apple)C++17
0 / 100
5 ms384 KiB
#include <iostream> #include <vector> #include <cstring> #include <cassert> #include <bitset> #include <iomanip> #include <algorithm> #pragma GCC optimize ("Ofast") #pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #pragma GCC optimize("unroll-loops") using namespace std; const int N = 1e9; struct Node { Node *l, *r; int sum; bool lazy; Node () { l = r = nullptr; sum = 0; lazy = false; } Node (bool value) { l = r = nullptr; sum = 0; lazy = value; } }; Node *root; void expandir (Node *cur) { if (cur == nullptr) { cur = new Node (true); } else { cur -> lazy = 1; } } void push (Node *cur, int lo, int hi) { cur -> sum = hi - lo + 1; if (lo != hi) { expandir (cur -> l); expandir (cur -> r); } cur -> lazy = 0; } int range_query (Node *cur, int ql, int qr, int lo, int hi) { if (cur == nullptr) return 0; if (cur -> lazy) push (cur, lo, hi); if (lo > qr || hi < ql) return 0; if (lo >= ql && hi <= qr) return cur -> sum; int mid = lo + (hi - lo) / 2; return range_query (cur -> l, ql, qr, lo, mid) + range_query (cur -> r, ql, qr, mid + 1, hi); } void range_set (Node *&cur, int ql, int qr, int lo, int hi) { if (cur == nullptr) cur = new Node; if (cur -> lazy) push (cur, lo, hi); if (lo > qr || hi < ql) return; if (lo >= ql && hi <= qr) { cur -> lazy = true; push (cur, lo, hi); return; } int mid = lo + (hi - lo) / 2; range_set (cur -> l, ql, qr, lo, mid); range_set (cur -> r, ql, qr, mid + 1, hi); cur -> sum = cur -> l -> sum + cur -> r -> sum; } int main () { ios::sync_with_stdio(0); cin.tie(0); root = new Node; int q; cin >> q; int C = 0; while (q--) { int task, lo, hi; cin >> task >> lo >> hi; --lo; --hi; lo += C; hi += C; if (task == 1) { // Range Query, update C C = range_query (root, lo, hi, 0, N); cout << C << '\n'; } else { // Range Set range_set (root, lo, hi, 0, N); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...