Submission #522405

#	Time	Username	Problem	Language	Result	Execution time	Memory
522405		sinfillo	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	227 ms	80884 KiB

apple

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cassert>
#include <stdio.h>
#include <algorithm>
#include <numeric>
#include <random>
#include <map>
#include <set>
#include <queue>
#include <fstream>
#include <deque>
#include <unordered_map>
#include <ctime>
#include <optional>
#include <stdexcept>
#include <cstring>
#include <math.h>

//#pragma GCC optimize("Ofast,fast-math,unroll-loops")


int MAX_N = 1E9 + 10;

struct __attribute__((__packed__)) Node{
    int sum;
    int push : 1;
    int left : 31;
    Node() {
        sum = 0;
        push = false;
        left = -1;
    }
};

const int MAX_SZ = 1E7 + 10;
int pt = 0;

Node sum[MAX_SZ];

struct Tree{

    void push(int ver, int left, int right) {
        if (!sum[ver].push) 
            return;
        if (sum[ver].left == -1) {
            sum[pt++] = Node(), sum[ver].left = pt - 1;
            sum[pt++] = Node();
        }
        int middle = (left + right) / 2;
        sum[sum[ver].left].sum = middle - left + 1;
        sum[sum[ver].left].push = 1;
        sum[sum[ver].left + 1].sum = right - middle;
        sum[sum[ver].left + 1].push = 1;
        sum[ver].push = 0;
        return;
    }

    int get_sum(int ver, int left, int right, int q_left, int q_right) {
        if (q_left > right || q_right < left)
            return 0;
        push(ver, left, right);
        if (left >= q_left && right <= q_right)
            return sum[ver].sum;
        int middle = (left + right) / 2;
        if (sum[ver].left == -1) {
            sum[pt++] = Node(), sum[ver].left = pt - 1;
            sum[pt++] = Node();
        }
        return get_sum(sum[ver].left, left, middle, q_left, q_right) + 
        get_sum(sum[ver].left + 1, middle + 1, right, q_left, q_right);
    }

    void update(int ver, int left, int right, int q_left, int q_right) {
        if (q_left > right || q_right < left) 
            return;
        push(ver, left, right);
        if (left >= q_left && right <= q_right) {
            sum[ver].sum = right - left + 1;
            sum[ver].push = 1;
            push(ver, left, right);
            return;
        }
        int middle = (left + right) / 2;
        if (sum[ver].left == -1) {
            sum[pt++] = Node(), sum[ver].left = pt - 1;
            sum[pt++] = Node();
        }
        update(sum[ver].left, left, middle, q_left, q_right);
        update(sum[ver].left + 1, middle + 1, right, q_left, q_right);
        sum[ver].sum = sum[sum[ver].left].sum + sum[sum[ver].left + 1].sum;
    }

};

signed main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int last = 0;
    int q;
    std::cin >> q;
    Tree tree;
    sum[pt++] = Node();
    while (q--) {
        int type, x, y;
        std::cin >> type >> x >> y;
        x += last, y += last;
        if (type == 2) {
            tree.update(0, 0, MAX_SZ, x, y);
        } else {
            last = tree.get_sum(0, 0, MAX_SZ, x, y);
            std::cout << last << '\n';
        }
    }
}

• Subtask 1: 0 / 100