Submission #1243092

#TimeUsernameProblemLanguageResultExecution timeMemory
1243092dudugynMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
294 ms205572 KiB
#include <bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define import <chatgpt>
//made by dudugyn :DD
#define int long long
#define f first
#define s second
#define pb push_back
#define sz(x) (int)(x.size())
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define endl '\n'
#define V vector
#define pii pair<int,int>
#define mem(x, v) memset((x), v, sizeof (x))
#define mid (l+r)/2
const int mod = (int)1e9+7;
const int inf = (int)LLONG_MAX;

template<class v>
auto operator<<(ostream &os, const vector<v> &vec)->ostream& {
    os << vec[0];
    for (size_t i = 1; i < vec.size(); i++) os << ' ' << vec[i];    
    os << '\n';
    return os;
}
template<class v>
auto operator>>(istream &is, vector<v> &vec)->istream& {
    for (auto &i : vec) is >> i;    
    return is;
}
template<class v>
auto operator<<(ostream &os, const vector<vector<v>> &vec)->ostream& {
    for (auto &i : vec) {
        os << i[0];
        for (size_t j = 1; j < i.size(); j++) os << ' ' << i[j];        
        os << '\n';
    }
    return os;
}
template<class v>
auto operator>>(istream  &is, vector<vector<v>> &vec)->istream& {
    for (auto &i : vec) 
        for (auto &j : i) is >> j;            
    return is;
}
struct Seg{
    struct No{
        int sum = 0, suml = 0;
        No *l_c = nullptr, *r_c = nullptr;
    };
    No *raiz = new No;
    void lazy(No *atual, int tam, int x){
        if(x == 1){
            atual->suml = x;
            atual->sum = x * tam;
        }
    }
    void prop(No* atual, int l, int r){
        if(!(atual->l_c)) (atual->l_c) = new No;
        if(!(atual->r_c)) (atual->r_c) = new No;
        lazy(atual->l_c, mid - l + 1, atual->suml);
        lazy(atual->r_c, r - mid, atual->suml);
    }
    void update(No* atual, int ql, int qr, int x, int l, int r){
        if(r < ql || l > qr)return;
        if(l >= ql && r <= qr){
            lazy(atual, r - l + 1, x);
            return;
        }
        prop(atual, l, r);
        update(atual->l_c, ql, qr, x, l, mid);
        update(atual->r_c, ql, qr, x, mid+1, r);
        (atual->sum) = (atual->l_c)->sum + (atual->r_c)->sum;
    }
    
    int query(No* atual, int ql, int qr, int l, int r){
        if(l >= ql && r <= qr)return atual->sum;
        if(r < ql || l > qr)return 0;
        prop(atual, l, r);
        return query(atual->l_c, ql, qr, l, mid) + 
            query(atual->r_c, ql, qr, mid+1, r);
    }
};
void solve(){
    int qq;
    cin >> qq;
    int c = 0;
    Seg seg;
    int n = 1e9+1;
    while(qq--){
        int op, l, r;
        cin >> op >> l >> r;
        if(op == 1){
            c = seg.query(seg.raiz, l + c, r + c, 0, n-1); 
            cout<<c<<endl;
        }else{
            seg.update(seg.raiz, l + c, r + c, 1, 0, n-1);
        }
    }
}
signed main() {
    ios;
    int tt=1;
    //cin>>tt;
    while(tt--){
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...