Submission #1264906

#TimeUsernameProblemLanguageResultExecution timeMemory
1264906nickolasarapidisMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
488 ms254584 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define F first #define S second #define pb push_back const long MAXN = 200000; struct node{ int sum, lazy; node *left, *right; node(int v = 0, int l = 0) : sum(v), lazy(l), left(nullptr), right(nullptr) {} }; void apply(node*& v){ if(!v) v = new node(); v->lazy = 1; } void update(node*& v, int l, int r, int a, int b){ if(!v) v = new node(); if(v->lazy == 1){ v->sum = r - l + 1; if(l != r){ apply(v->left); apply(v->right); } v->lazy = 0; } if(l > b or r < a) return; if(l >= a and r <= b){ v->sum = r - l + 1; if(l != r){ apply(v->left); apply(v->right); } return; } int m = (l + r)/2; update(v->left, l, m, a, b); update(v->right, m + 1, r, a, b); v->sum = (v->left)->sum + (v->right)->sum; return; } int query(node*& v, int l, int r, int a, int b){ if(!v) v = new node(); if(v->lazy == 1){ v->sum = r - l + 1; if(l != r){ apply(v->left); apply(v->right); } v->lazy = 0; } if(l > b or r < a) return 0; if(l >= a and r <= b) return v->sum; int m = (l + r)/2; return query(v->left, l, m, a, b) + query(v->right, m + 1, r, a, b); } int main(){ int M, C = 0; cin >> M; node *root = new node(); for(int i = 0; i < M; i++){ int d, l, r; cin >> d >> l >> r; if(d == 1){ C = query(root, 0, 1e9 - 1, l + C, r + C); cout << C << "\n"; } else{ update(root, 0, 1e9 - 1, l + C, r + C); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...