제출 #1290217

#제출 시각아이디문제언어결과실행 시간메모리
1290217matematteo원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
1 ms332 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
using namespace std;
#define ll long long
#define f first 
#define s second
class segtree{
    private:
    struct Nd{
        ll sum=0,lz=0;
        Nd *left=nullptr;
        Nd *right=nullptr;
    };
    Nd *root=new Nd;
    const ll n;
    ll com (ll a, ll b) {return a+b;}
    void apply(Nd *cur,ll sz,ll val){
        if (val){
            cur->lz=val;
            cur->sum=sz*val;
        }
    }
    void prop(Nd *cur, ll l, ll r){
        if (cur->left=nullptr) cur->left=new Nd;
        if (cur->right=nullptr) cur->right=new Nd;
        ll m=(l+r)/2;
        apply(cur->left,m-l,cur->lz);
        apply(cur->right,r-m,cur->lz);
    }
    void sett(Nd *cur,ll l, ll r, ll a,ll b, ll val){
        if (b<=l||r<=a) return;
        if (l<=a&&b<=r){
            apply(cur,b-a,val);
            return;
        }
        prop(cur,a,b);
        ll m=(a+b)/2;
        sett(cur->left,l,r,a,m,val);
        sett(cur->right,l,r,m,b,val);
        cur->sum=(cur->left)->sum+(cur->right)->sum;
    }
    ll querì(Nd *cur,ll l,ll r,ll a,ll b){
        if (r<=a||b<=l) return 0;
        if (l<=a&&b<=r) return cur->sum;
        prop(cur,a,b);
        ll m=(a+b)/2;
        return (querì(cur->left,l,r,a,m)+querì(cur->right,l,r,m,b));
    }

    public:
        segtree(ll n) : n(n){}
        void cap(ll a,ll b, ll val) {sett(root,0,n,a,b+1,val);}
        ll sum(ll a,ll b){return querì(root,0,n,a,b+1);}
};
int main(){
    int M;
    cin >> M;
    segtree oo((const ll)1e18);
    ll d=0;
    for (int a,b,c,i=0;i<M;i++){
        cin >> a >> b >> c;
        if (a==1){
            d=oo.sum(b+d,c+d);
            cout << d << "\n";
            continue;
        }
        oo.cap(b+d,c+d,1);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...