# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
986080 | Haboosh915 | Monkey and Apple-trees (IZhO12_apple) | C++17 | 349 ms | 262144 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |