Submission #986080

#	Time	Username	Problem	Language	Result	Execution time	Memory
986080		Haboosh915	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	349 ms	262144 KiB

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(1000000000) ;
    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: 0 / 100