제출 #709513

#제출 시각아이디문제언어결과실행 시간메모리
709513Rasoul006원숭이와 사과 나무 (IZhO12_apple)C++17
0 / 100
1 ms340 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 (!laz[n])
        return ;
 
    if (!L[n])
        L[n] = ++id ;
    if (!R[n])
        R[n] = ++id ;
 
    tree[n] = r - l + 1 ;
    laz[L[n]] = true ;
    laz[R[n]] = true ;
    laz[n] = false ;
    
    return ;
}
 
void upd (ll n , ll l , ll r , ll x , ll y)
{
    if (l > y || r < x)
        return ;
 
    push(n , l , r) ;
 
    if (x <= l && r <= y)
    {
        laz[n] = true ;
        push(n , l , r) ;
        return ;
    }
 
    if (!L[n])
        L[n] = ++id;
    if (!R[n])
        R[n] = ++id;
 
    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 = (!L[n] ? 0 : query(L[n] , l , mid , x , y)) ;
    ll ri = (!R[n] ? 0 : 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...