답안 #986085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986085	2024-05-19T17:49:14 Z	Haboosh915	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	354 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(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

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 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	8284 KB	Output is correct
5	Correct	17 ms	10032 KB	Output is correct
6	Correct	16 ms	9564 KB	Output is correct
7	Correct	16 ms	9964 KB	Output is correct
8	Correct	135 ms	74068 KB	Output is correct
9	Correct	289 ms	131156 KB	Output is correct
10	Correct	293 ms	141200 KB	Output is correct
11	Correct	312 ms	153696 KB	Output is correct
12	Correct	315 ms	158828 KB	Output is correct
13	Correct	296 ms	200688 KB	Output is correct
14	Correct	291 ms	202832 KB	Output is correct
15	Runtime error	354 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-