Submission #1329593

#TimeUsernameProblemLanguageResultExecution timeMemory
1329593efegMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
500 ms260496 KiB
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back

using i64 = long long; 
template<typename T>
using vec = vector<T>; 
using pi = pair<int,int>; 

struct Node{
    int val,lazy = 0;
    Node *l = NULL,*r = NULL; 
    Node (int val) : val(val) {}
    Node (int val,Node* l,Node* r) : val(val) , l(l) , r(r) {}
}; 

struct SegTree{
    int n; vec<Node> tree; 
    Node* root; 
    SegTree(){
        root = new Node(0); 
    }

    void push(Node* node,int s,int e){
        if (node->lazy == 0) return; 
        node->val = (e-s+1); 

        if (s != e){
            if (node->l == NULL) node->l = new Node(0); 
            if (node->r == NULL) node->r = new Node(0); 
            node->l->lazy = node->lazy; 
            node->r->lazy = node->lazy;
        }
        node->lazy = 0; 
    }
    
    void update(Node *node,int s,int e,int l,int r,int v){
        push(node,s,e); 
        if (r < s || e < l) return; 
        if (l <= s && e <= r){
            node->lazy = v; 
            push(node,s,e); 
            return; 
        }
        int m = (s+e) / 2; 
        if (node->l == NULL) node->l = new Node(0); 
        if (node->r == NULL) node->r = new Node(0); 

        update(node->l,s,m,l,r,v); 
        update(node->r,m+1,e,l,r,v); 
        
        node->val = node->l->val + node->r->val;
    }

    int query(Node *node,int s,int e,int l,int r){
        push(node,s,e); 
        if (r < s || e < l) return 0; 
        if (l <= s && e <= r) return node->val; 
        int m = (s+e) / 2; 
        if (node->l == NULL) node->l = new Node(0);  
        if (node->r == NULL) node->r = new Node(0);  
        return query(node->l,s,m,l,r) + query(node->r,m+1,e,l,r); 
    }

    void update(int l,int r,int v){ update(root,1,1e9,l,r,v); }
    int query(int l,int r){return query(root,1,1e9,l,r); }

}; 


int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 
    int n,c = 0; cin >> n; 
    
    SegTree tree; 
    while (n--){
        int d,x,y; cin >> d >> x >> y;
        x+=c; y+=c; 
        if (d == 2){
            tree.update(x,y,1); 
        }
        else {
            c = tree.query(x,y); 
            cout << c << endl; ; 
            
        }
    }


    return 0; 

}
#Verdict Execution timeMemoryGrader output
Fetching results...