Submission #1308839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308839		a5a7	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	270 ms	137340 KiB

apple

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct SparseNode{
    SparseNode *left = NULL, *right = NULL;
    int freq = 0;
    bool lazy = false;
    SparseNode() {};
};

void push_down(SparseNode *curr, int curr_left, int curr_right){
    if (!curr->left) curr->left = new SparseNode;
    if (!curr->right) curr->right = new SparseNode;
    int m = (curr_left+curr_right)/2;
    if (curr->lazy){
        curr->left->lazy = true;
        curr->right->lazy = true;
        curr->right->freq = (curr_right - m);
        curr->left->freq = (m - curr_left + 1);
    }
}

void paint(SparseNode *curr, int curr_left, int curr_right, int query_left, int query_right){
    if (curr_left > query_right || curr_right < query_left) return;
    if (query_left <= curr_left && curr_right <= query_right){
        curr->lazy = true;
        curr->freq = curr_right - curr_left+1;
        return;
    }
    push_down(curr, curr_left, curr_right);
    int m = (curr_left+curr_right)/2;
    paint(curr->left, curr_left, m, query_left, query_right);
    paint(curr->right, m+1, curr_right, query_left, query_right);
    curr->freq = curr->left->freq + curr->right->freq;
}

int sum(SparseNode *curr, int curr_left, int curr_right, int query_left, int query_right){
    if (curr_left > query_right || curr_right < query_left) return 0;
    if (query_left <= curr_left && curr_right <= query_right) {
        return curr->freq;
    }
    push_down(curr, curr_left, curr_right);
    int m = (curr_left+curr_right)/2;
    return sum(curr->left, curr_left, m, query_left, query_right) + sum(curr->right, m+1, curr_right, query_left, query_right);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int m; cin >> m;
    SparseNode *root = new SparseNode;
    int c = 0;
    while (m--){
        int d, x, y; cin >> d >> x >> y;
        if (d == 1){
            c = sum(root, 1, 1000000000, x+c, y+c);
            cout << c << "\n";
        }else{
            paint(root, 1, 1000000000, x+c, y+c);
        }
    }
}

• Subtask 1: 100 / 100