Submission #1354692

#TimeUsernameProblemLanguageResultExecution timeMemory
1354692hyyhMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
393 ms254580 KiB
#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <iomanip>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cstdlib>

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x),end(x)

int const N = 1<<30;

struct Node{
    int val;
    int lazy;
    Node *left;
    Node *right;

    Node(int n) : val(n),lazy(0),left(nullptr),right(nullptr) {}

    void renew(){
        val = 0;
        if(left) val += left->val;
        if(right) val += right->val;
    }

    void extend(){
        if(!left) left = new Node(0);
        if(!right) right = new Node(0);
    }
};

Node *root = new Node(0);

void push(Node *node,int l,int r){
    if(!node) return;
    if(node->lazy){
        if(l != r){
            node->extend();
            node->left->lazy = node->right->lazy = node->lazy;
            int md = l+(r-l)/2;
            node->left->val = md-l+1;
            node->right->val = r-md;
        }
        node->lazy = 0;
    }
}

void update(Node *node,int l,int r,int ql,int qr){
    push(node,l,r);
    if(l >= ql && r <= qr){
        node->val = r-l+1;
        node->lazy = 1;
        push(node,l,r);
    }
    else if(l > qr || r < ql) return;
    else{
        int md = l+(r-l)/2;
        node->extend();
        update(node->left,l,md,ql,qr);
        update(node->right,md+1,r,ql,qr);
        node->renew();
    }
}

int query(Node* node,int l,int r,int ql,int qr){
    push(node,l,r);
    if(l >= ql && r <= qr) return node->val;
    else if(l > qr || r < ql) return 0;
    else{
        int md = l+(r-l)/2;
        node->extend();
        int q1 = query(node->left,l,md,ql,qr);
        int q2 = query(node->right,md+1,r,ql,qr);
        return q1+q2;
    }
}

int main(){
    int q;cin >> q;
    int c = 0;
    for(int i{};i < q;i++){
        int d,a,b;cin >> d >> a >> b;
        if(d == 2) update(root,1,N,a+c,b+c);
        else c = query(root,1,N,a+c,b+c), cout << c << endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...