제출 #468341

#제출 시각아이디문제언어결과실행 시간메모리
468341jenishmonpara원숭이와 사과 나무 (IZhO12_apple)C++14
100 / 100
506 ms134372 KiB

#include <bits/stdc++.h>
using namespace std;
long double PI = acos(-1);
long double DEL = 1e-12;
long long M =  1e9 + 7;
const long long N = 3e5 + 10;
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#define ftt cin>>tc;for(int cas=1;cas<=tc;++cas)
#define all(a) a.begin(),a.end()
#define sq(a) ((a)*(a))
#define double long double
#define dbg cout<<"\nhi\n";
//#define int long long
#define nl cout<<"\n"
#define sp <<" "<<
#define mid ((l+r)>>1)
#define X real()
#define Y imag()


//*********************************** CHECK CONSTRAINTS ***********************************
int cnt, sum, mx, mn, ans, a[N], b[N];
int n, m, d, i, j, k, l, p, q, r, t, w, x, y, z, tc;
string s;



//************************************* CODE STARTS ****************************************

struct node{
        int s,lz,lson,rson;
        node() : s(0),lz(0),lson(0),rson(0){}
};

vector<node> seg;

void push(int i,int l,int r){
        if(seg[i].lz == 0){
                return;
        }
        seg[i].s = r - l + 1;
        if(l != r){
                if(seg[i].lson == 0){
                        seg[i].lson=seg.size();
                        seg.emplace_back();
                        seg[i].rson=seg.size();
                        seg.emplace_back();
                }
                seg[seg[i].lson].lz = seg[seg[i].rson].lz = 1;
        }
        seg[i].lz=0;
}

void upd(int i,int l,int r,int a,int b){
        push(i,l,r);
        if(l > b or r < a){
                return;
        }
        if(a <= l and r <= b){
                seg[i].lz = 1;
                push(i,l,r);
                return;
        }
        if(seg[i].lson == 0){
                seg[i].lson=seg.size();
                seg.emplace_back();
                seg[i].rson=seg.size();
                seg.emplace_back();
        }
        upd(seg[i].lson,l,mid,a,b);
        upd(seg[i].rson,mid+1,r,a,b);
        seg[i].s = seg[seg[i].lson].s + seg[seg[i].rson].s;
}

int get(int i,int l,int r,int a,int b){
        push(i,l,r);

        if(l > b or r < a or seg[i].s == 0){
                return 0;
        }
        if(a <= l and r <= b){
                return seg[i].s;
        }
        
        return get(seg[i].lson,l,mid,a,b) + get(seg[i].rson,mid+1,r,a,b);

}

int32_t main()
{
        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#ifndef ONLINE_JUDGE
//        freopen("/Users/jenish/XCode/cp/input.txt","r",stdin);
//#endif
        seg.emplace_back();
        seg.emplace_back();
        int c = 0;
        ftt{
                cin >> x >> l >> r;
                if(x == 1){
                        c = get(1,-2e9,2e9,c+l,c+r);
                        cout<<c;nl;
                }
                else{
                        upd(1,-2e9,2e9,c+l,c+r);
                }
        }
}




#Verdict Execution timeMemoryGrader output
Fetching results...