Submission #986083

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986083	2024-05-19T17:48:47 Z	Haboosh915	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	426 ms	254548 KB

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

//#define int long long
#define ll long long
#define F first
#define S second
#define endl '\n'
#define all(x) x.begin() , x.end()
#define FIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const long long mod = 998244353 , Inf = 1e17 ;
const int N = 100005 , inf = INT_MAX ;
int mvi[] = {1 , -1 , 0 , 0 , 1 , 1 , -1 , -1 } ;
int mvj[] = {0 , 0 , 1 , -1 , 1 , -1 , 1 , -1 } ;

struct node {
    int val ;
    bool operation ;
    node *l , *r ;

    node ( int x ) : val(x) , l(nullptr) , r(nullptr) {}
    node ( node *L = nullptr , node *R = nullptr ) {
        l = L ; r = L ;
        val = 0 ; operation = false ;
    }
};

struct Seg {
    node *root ;
    int size = 1 ;
    void init ( int n ) {
        root = new node() ;
        while ( size < n ) size *= 2 ;
    }

    void propagate ( node *x , int lx , int rx ) {
        if ( lx == rx || !(x->operation) ) return ;
        if ( x->l == nullptr ) x->l = new node() ;
        if ( x->r == nullptr ) x->r = new node() ;
        int mid = (lx+rx)/2 ;
        x->l->val = (mid-lx+1) ; x->l->operation = true ;
        x->r->val = (rx-mid) ;   x->r->operation = true ;
        x->operation = false ;
        x->val = x->l->val + x->r->val ;
    }

    void set ( int l , int r , node *x , int lx , int rx ) {
        propagate ( x , lx , rx ) ;
        if ( lx >= l && rx <= r ) {
            x->val = (rx-lx+1) ;
            x->operation = true ;
            return ;
        }
        if ( lx > r || rx < l ) return ;
        int mid = (lx+rx)/2 ;
        if ( x->l == nullptr ) x->l = new node() ;
        if ( x->r == nullptr ) x->r = new node() ;
        set ( l , r , x->l , lx , mid ) ;
        set ( l , r , x->r , mid+1 , rx ) ;
        x->val = x->l->val + x->r->val ;
    }

    void set ( int l , int r ) {
        set ( l , r , root , 1 , size ) ;
    }

    int get ( int l , int r , node *x , int lx , int rx ) { //cout << lx << ' ' << rx << endl ;
        propagate (x , lx , rx) ;
        if ( lx >= l && rx <= r ) return x->val ;
        if ( lx > r || rx < l ) return 0 ;
        int mid = (lx+rx)/2 ;
        if ( x->l == nullptr ) x->l = new node() ;
        if ( x->r == nullptr ) x->r = new node() ;
        int s1 = get(l , r , x->l , lx , mid) ;
        int s2 = get(l , r , x->r , mid+1 , rx) ;
        return s1 + s2 ;
    }

    int get ( int l , int r ) {
        return get ( l , r , root , 1 , size ) ;
    }
};

int32_t main() { FIO ;

    int m ; cin >> m ;
    Seg st ; st.init(1000000001) ;
    int c = 0 ;
    while ( m-- ) {
        int op ; cin >> op ;
        if ( op == 2 ) {
            int l , r ; cin >> l >> r ;
            st.set(l+c , r+c) ;
        } else {
            int l , r ; cin >> l >> r ;
            c = st.get(l+c , r+c) ;
            cout << c << endl ;
        }
    }

    return 0 ;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	11 ms	5724 KB	Output is correct
5	Correct	14 ms	6748 KB	Output is correct
6	Correct	13 ms	6492 KB	Output is correct
7	Correct	14 ms	6812 KB	Output is correct
8	Correct	111 ms	49492 KB	Output is correct
9	Correct	235 ms	87632 KB	Output is correct
10	Correct	259 ms	94604 KB	Output is correct
11	Correct	253 ms	102740 KB	Output is correct
12	Correct	256 ms	106072 KB	Output is correct
13	Correct	244 ms	134228 KB	Output is correct
14	Correct	246 ms	135416 KB	Output is correct
15	Correct	426 ms	246472 KB	Output is correct
16	Correct	410 ms	248396 KB	Output is correct
17	Correct	258 ms	140400 KB	Output is correct
18	Correct	253 ms	140216 KB	Output is correct
19	Correct	426 ms	254400 KB	Output is correct
20	Correct	423 ms	254548 KB	Output is correct