Submission #895546

#TimeUsernameProblemLanguageResultExecution timeMemory
895546abysmal원숭이와 사과 나무 (IZhO12_apple)C++14
100 / 100
292 ms136172 KiB
#include<iostream> #include<stdio.h> #include<stdint.h> #include<vector> #include<algorithm> #include<utility> #include<set> #include<map> #include<queue> #include<stack> #include<iomanip> #include<string> #include<math.h> #include<assert.h> using namespace std; const double PI = (double) atan(1.0) * 4; const int64_t INF = (int64_t) 5e18 + 777; const int64_t mINF = (int64_t) 1e6 + 777; const int64_t offset = (int64_t) 1e6 + 777; const int64_t MOD = 1e9 + 7; const int nbit = 19; const int ndig = 10; const int nchar = 26; const int p1 = 31; const int p2 = 53; const int D = 4; int dr[D] = {0, 1, 0, -1}; int dc[D] = {1, 0, -1, 0}; // 0 right // 1 down // 2 left // 3 up struct Node { int sum; int tag; Node* left; Node* right; Node(int sum_ = 0, int tag_ = 0) : sum(sum_), tag(tag_) { left = NULL; right = NULL; } }; struct Tree { Node* root; Tree() { root = new Node(); } void update(Node* cur, int nleft, int nright, int left, int right) { if(left > nright || nleft > right) return; int len = nright - nleft + 1; if(left <= nleft && nright <= right) { cur->tag++; cur->sum = len; return; } push(cur, len / 2); int mid = nleft + (nright - nleft) / 2; if(cur->left == NULL) cur->left = new Node(); if(cur->right == NULL) cur->right = new Node(); update(cur->left, nleft, mid, left, right); update(cur->right, mid + 1, nright, left, right); cur->sum = cur->left->sum + cur->right->sum; } int get(Node* cur, int nleft, int nright, int left, int right) { if(cur == NULL) return 0; if(left > nright || nleft > right) return 0; if(left <= nleft && nright <= right) return cur->sum; int len = nright - nleft + 1; push(cur, len / 2); int mid = nleft + (nright - nleft) / 2; return get(cur->left, nleft, mid, left, right) + get(cur->right, mid + 1, nright, left, right); } void updateRange(int l, int r) { update(root, 1, (1 << 30), l, r); } int query(int l, int r) { return get(root, 1, (1 << 30), l, r); } void push(Node* i, int len) { if(i->tag == 0) return; if(i->left == NULL) i->left = new Node(); if(i->right == NULL) i->right = new Node(); i->left->tag += i->tag; i->left->sum = len; i->right->tag += i->tag; i->right->sum = len; i->tag = 0; } }; struct Solution { Solution() {} void solve() { int n; cin >> n; int c = 0; Tree tree; for(int i = 0; i < n; i++) { int t; int x; int y; cin >> t >> x >> y; x += c; y += c; if(t == 1) { c = tree.query(x, y); cout << c << "\n"; } else tree.updateRange(x, y); } } int modsub(int t1, int t2) { int res = t1 - t2; if(res < 0) res += MOD; return res; } bool BIT(int& mask, int& j) { return (mask & MASK(j)); } int64_t Abs(int64_t t1) { if(t1 < 0) return -t1; return t1; } int MASK(int j) { return (1 << j); } }; void __startup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); } int main() { __startup(); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { Solution().solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...