Submission #1284372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284372		Iwantbemaster	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	28 ms	2712 KiB

apple

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int l, r;
    long long sum;
    bool lazy;
    Node *left, *right;
    Node(int l, int r) : l(l), r(r), sum(0), lazy(false), left(nullptr), right(nullptr) {}
};
void update(Node* node, int l, int r) {
    if(l > node -> r || r < node -> l) return;
    if(node -> lazy) return;
    if(l <= node -> l && node -> r <= r){
        node -> sum = node -> r - node -> l + 1;
        node -> lazy = true; return;
    } int mid = node -> l + (node -> r - node -> l) / 2;
    if(node -> left == nullptr){
        node -> left = new Node(node -> l, mid);
        node -> right = new Node(mid + 1, node -> r);
    } update(node -> left, l, r);
    update(node -> right, l, r);
    node -> sum = node -> left -> sum + node -> right -> sum;
}
long long query(Node* node, int l, int r){
    if(l > node -> r || r < node -> l) return 0;
    if(node -> lazy) return min(r, node -> r) - max(l, node -> l) + 1;
    if(l <= node -> l && node -> r <= r) return node-> sum;
    int mid = node -> l + (node -> r - node -> l) / 2;
    if(node -> left == nullptr){
        node -> left = new Node(node -> l, mid);
        node -> right = new Node(mid + 1, node -> r);
    } return query(node -> left, l, r) + query(node -> right, l, r);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int M; cin >> M;
    Node* root = new Node(1, 1000000000);
    int C = 0;
    for(int i = 0; i < M; i++){
        int D, X, Y; cin >> D >> X >> Y;
        int l = X + C;
        int r = Y + C;
        if(D == 1){
            long long ans = query(root, l, r);
            cout << ans << '\n';
            C = ans;
        } else update(root, l, r);
    } return 0;
}

• Subtask 1: 100 / 100