제출 #709879

#제출 시각아이디문제언어결과실행 시간메모리
709879Rasoul006원숭이와 사과 나무 (IZhO12_apple)C++14
100 / 100
480 ms236160 KiB
#include <bits/stdc++.h>

#define endl "\n"

#define F first

#define S second

#define pb push_back

#define all(x) x.begin() , x.end()

#define mm(dp , val) memset (dp , val , sizeof dp)

#define mid ((r+l)>>1)

#define lx (n<<1)

#define rx ((n<<1)|1)

#define low (i&(-i))

#define lb lower_bound

#define ub upper_bound

#define no void (cout << "NO" << endl)

#define one void (cout << "-1" << endl)

#define zer void (cout << "0" << endl)

#define yes void (cout << "YES" << endl)

typedef long long ll;

using namespace std;

const int logn = 26 ;

const int N = 1e7+5;

const int mod = 1e9+7;

const long long oo = 4557430888798830399 ;

ll dx[] = {0 , 0 , 1 , -1};
ll dy[] = {1 , -1 , 0 , 0};

ll id = 1 , n , a[N] , tree[N] , laz[N] , L[N] , R[N] ;

void push (ll n , ll l , ll r)
{
    if (!L[n])
        L[n] = ++id;
    if (!R[n])
        R[n] = ++id;

    if (!laz[n])
        return ;
    tree[n] = r - l + 1 ;

    laz[L[n]] = true ;
    laz[R[n]] = true ;
    return ;
}

void upd (ll n , ll l , ll r , ll x , ll y)
{
    push(n , l , r) ;

    if (l > y || r < x)
        return ;

    if (x <= l && r <= y)
    {
        laz[n] = true ;
        push(n , l , r) ;
        return ;
    }

    upd(L[n] , l , mid , x , y) ;
    upd(R[n] , mid+1 , r , x , y) ;

    tree[n] = tree[L[n]] + tree[R[n]] ;
}

ll query (ll n , ll l , ll r , ll x , ll y)
{

    if (l > y || r < x)
        return 0 ;

    push(n , l , r);

    if (x <= l && r <= y)
        return tree[n] ;

    ll le = query(L[n] , l , mid , x , y) ;
    ll ri = query(R[n] , mid+1 , r , x , y) ;

    return le + ri ;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n ;

    ll c = 0 ;

    while (n--)
    {
        ll ty , l , r ;
        cin >> ty >> l >> r ;

        if (ty == 2)
            upd(1 , 0 , (1ll<<32) , l + c , r + c) ;
        else
        {
            ll p = query (1 , 0 , (1ll<<32) , l + c , r + c) ;
            cout << p  << endl ;
            c = p ;
        }
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...