제출 #986080

#제출 시각아이디문제언어결과실행 시간메모리
986080Haboosh915Monkey and Apple-trees (IZhO12_apple)C++17
0 / 100
349 ms262144 KiB
#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 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...