Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- const int size = 1e5 + 1;
- const int min = -1e9;
- const int max = 1e9;
- using std::cin;
- using std::cout;
- using std::vector;
- void maxBuilding(vector<int>& tree, vector<int>& a, int v, int tl, int tr) {
- if (tl == tr) {
- tree[v] = a[tl];
- return;
- }
- int tm = (tl + tr) >> 1;
- maxBuilding(tree, a, 2 * v, tl, tm);
- maxBuilding(tree, a, 2 * v + 1, tm + 1, tr); //мб тут нужна проверка того что сын существует
- tree[v] = std::max(tree[2*v], tree[2*v + 1]);
- }
- int getMax(vector<int>& tree, int v, int tl, int tr, int l, int r) {
- if (tl == l && tr == r) {
- return tree[v];
- }
- int tm = (tl + tr) >> 1;
- int ans = min;
- if (l <= tm) {
- int temp_ans = getMax(tree, 2*v, tl, tm, l, std::min(r, tm));
- ans = std::max(temp_ans, ans);
- }
- if (r >= tm + 1) {
- int temp_ans = getMax(tree, 2*v + 1, tm + 1, tr, std::max(tm + 1, tl), r);
- ans = std::max(temp_ans, ans);
- }
- return ans;
- }
- void maxUpdate(vector<int>& tree, int v, int tl, int tr, int pos, int val) {
- tree[v] = std::max(tree[v], val);
- if (tl == tr) {
- return;
- }
- int tm = (tl + tr) >> 1;
- if (pos <= tm) {
- maxUpdate(tree, 2*v, tl, tm, pos, val);
- } //а может можно и else
- if (pos >= tm + 1) {
- maxUpdate(tree, 2*v + 1, tm + 1, tr, pos, val);
- }
- }
- void minBuilding(vector<int>& tree, vector<int>& a, int v, int tl, int tr) {
- if (tl == tr) {
- tree[v] = a[tl];
- return;
- }
- int tm = (tl + tr) >> 1;
- minBuilding(tree, a, 2 * v, tl, tm);
- minBuilding(tree, a, 2 * v + 1, tm + 1, tr); //мб тут нужна проверка того что сын существует
- tree[v] = std::min(tree[2*v], tree[2*v + 1]);
- }
- int getMin(vector<int>& tree, int v, int tl, int tr, int l, int r) {
- if (tl == l && tr == r) {
- return tree[v];
- }
- int tm = (tl + tr) >> 1;
- int ans = max;
- if (l <= tm) {
- int temp_ans = getMin(tree, 2*v, tl, tm, l, std::min(r, tm));
- ans = std::min(temp_ans, ans);
- }
- if (r >= tm + 1) {
- int temp_ans = getMin(tree, 2*v + 1, tm + 1, tr, std::max(tm + 1, tl), r);
- ans = std::min(temp_ans, ans);
- }
- return ans;
- }
- void minUpdate(vector<int>& tree, int v, int tl, int tr, int pos, int val) {
- tree[v] = std::min(tree[v], val);
- if (tl == tr) {
- return;
- }
- int tm = (tl + tr) >> 1;
- if (pos <= tm) {
- minUpdate(tree, 2*v, tl, tm, pos, val);
- } //а может можно и else
- if (pos >= tm + 1) {
- minUpdate(tree, 2*v + 1, tm + 1, tr, pos, val);
- }
- }
- int main() {
- std::ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int m;
- cin >> m;
- vector<int> v(size + 1);
- for (int i = 1; i <= size; i++) { //если i = 0 то будет ли разница?
- int a = ((i % 12345) * (i % 12345)) % 12345;
- int c = ((i % 23456) * (i % 23456)) % 23456;
- int b = (c * (i % 23456)) % 23456;
- v[i] = a + b;
- }
- vector<int> max_tree(4 * size);
- maxBuilding(max_tree, v, 1, 0, size - 1);
- vector<int> min_tree(4 * size);
- minBuilding(min_tree, v, 1, 0, size - 1);
- for (int i = 1; i <= m; i++) {
- int xi, yi;
- cin >> xi >> yi;
- if (xi > 0) {
- int maximum = getMax(max_tree, 1, 0, size, xi, yi);
- int minimum = getMin(min_tree, 1, 0, size, xi, yi);
- cout << maximum - minimum << "\n";
- }
- if (xi < 0) {
- xi *= -1;
- maxUpdate(max_tree, 1, 0, size, xi, yi);
- minUpdate(min_tree, 1, 0, size, xi, yi);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement