제출 #1178625

#제출 시각아이디문제언어결과실행 시간메모리
1178625rewqewMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
0 ms320 KiB
#include <iostream>
#include <vector>

struct Node {
    int l;
    int r;
    int m;
    long long ripe = 0;
    long long prefix = 0;

    Node *lChild = NULL;
    Node *rChild = NULL;

    Node(int _l, int _r) {
        l = _l;
        r = _r;
        m = (l+r)/2;
    }

    int Update(int a, int b) {
        if (l == r) {
            ripe = 1;
            return 1;
        }

        ripe = 0;
        if (lChild == NULL) {
            lChild = new Node(l, m);
        }
        if (a <= m) {
            ripe += lChild->Update(a, b);
        }
        else {
            ripe += lChild->ripe;
        }
        
        if (rChild == NULL) {
            rChild = new Node(m+1, r);
        }
        if (m <= b) {
            ripe += rChild->Update(a, b);
        }
        else {
            ripe += rChild->ripe;
        }

        return ripe;
    }

    long long Sum(int a, int b) {
        if (l >= a && r <= b) {
            return ripe;
        }

        if (l > b || r < a) {
            return 0;
        }

        long long sum = 0;
        if (a <= m) {
            if (lChild == NULL) {
                lChild = new Node(l, m);
            }
            sum += lChild->Sum(a, b);
        }
        if (m <= b) {
            if (rChild == NULL) {
                rChild = new Node(m+1, r);
            }
            sum += rChild->Sum(a, b);
        }
        return sum;
    }
};


int main() {
    int m;
    std::cin >> m;
    Node root(0, 2000000000);
    for (int i = 0; i < m; i++) {
        int d, x, y;
        std::cin >> d >> x >> y;
        x--;
        y--;

        if (d == 1) {
            std::cout << root.Sum(x, y) << "\n";
        }   
        else {
            root.Update(x, y);
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...