Submission #709879

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
709879	2023-03-14T18:32:09 Z	Rasoul006	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	480 ms	236160 KB

apple

#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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	18 ms	5716 KB	Output is correct
5	Correct	17 ms	6684 KB	Output is correct
6	Correct	18 ms	6412 KB	Output is correct
7	Correct	23 ms	6684 KB	Output is correct
8	Correct	180 ms	49724 KB	Output is correct
9	Correct	313 ms	90268 KB	Output is correct
10	Correct	325 ms	95632 KB	Output is correct
11	Correct	318 ms	102800 KB	Output is correct
12	Correct	364 ms	105804 KB	Output is correct
13	Correct	281 ms	124940 KB	Output is correct
14	Correct	304 ms	126336 KB	Output is correct
15	Correct	453 ms	229284 KB	Output is correct
16	Correct	455 ms	230836 KB	Output is correct
17	Correct	285 ms	130596 KB	Output is correct
18	Correct	296 ms	130620 KB	Output is correct
19	Correct	407 ms	235928 KB	Output is correct
20	Correct	480 ms	236160 KB	Output is correct