Submission #986080

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986080	2024-05-19T17:43:30 Z	Haboosh915	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	349 ms	262144 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(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.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	348 KB	Output is correct
4	Correct	13 ms	8792 KB	Output is correct
5	Correct	17 ms	10076 KB	Output is correct
6	Correct	16 ms	9820 KB	Output is correct
7	Correct	17 ms	10328 KB	Output is correct
8	Correct	149 ms	74896 KB	Output is correct
9	Correct	315 ms	132792 KB	Output is correct
10	Correct	309 ms	143188 KB	Output is correct
11	Correct	329 ms	155316 KB	Output is correct
12	Correct	321 ms	160592 KB	Output is correct
13	Correct	299 ms	202832 KB	Output is correct
14	Correct	302 ms	204912 KB	Output is correct
15	Runtime error	349 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-