Submission #522405

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
522405	2022-02-04T21:52:52 Z	sinfillo	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	227 ms	80884 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	78540 KB	Output is correct
2	Correct	34 ms	78540 KB	Output is correct
3	Correct	34 ms	78524 KB	Output is correct
4	Correct	43 ms	78688 KB	Output is correct
5	Correct	44 ms	78756 KB	Output is correct
6	Correct	48 ms	78664 KB	Output is correct
7	Correct	45 ms	78680 KB	Output is correct
8	Correct	113 ms	79616 KB	Output is correct
9	Correct	204 ms	80620 KB	Output is correct
10	Correct	212 ms	80644 KB	Output is correct
11	Correct	227 ms	80620 KB	Output is correct
12	Correct	225 ms	80752 KB	Output is correct
13	Incorrect	69 ms	80884 KB	Output isn't correct
14	Halted	0 ms	0 KB	-