# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
950287 | nguyennh | Monkey and Apple-trees (IZhO12_apple) | C++14 | 115 ms | 262144 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define el '\n'
using namespace std ;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
const int MN = 123456;
struct Node{
int sum , lazy , l , r , child_l , child_r;
Node () : sum(0) , lazy(0) , child_l(-1) , child_r(-1) {};
};
Node st[64 * MN];
int node = 2;
void fix(int id){
if (!st[id].lazy) return;
st[id].sum = st[id].r - st[id].l + 1;
int mid = st[id].l + st[id].r >> 1;
if (st[id].child_l == -1){
st[id].child_l = node++;
st[st[id].child_l].l = st[id].l;
st[st[id].child_l].r = mid;
st[st[id].child_l].lazy = 1;
}
if (st[id].child_r == -1){
st[id].child_r = node++;
st[st[id].child_r].l = mid + 1;
st[st[id].child_r].r = st[id].r;
st[st[id].child_r].lazy = 1;
}
st[id].lazy = 0;
}
void update(int id , int l , int r){
fix(id);
if (st[id].l == l && st[id].r == r){
st[id].lazy = 1;
fix(id);
return;
}
else {
int mid = st[id].l + st[id].r >> 1;
if (st[id].child_l == -1){
st[id].child_l = node++;
st[st[id].child_l].l = st[id].l;
st[st[id].child_l].r = mid;
}
if (st[id].child_r == -1){
st[id].child_r = node++;
st[st[id].child_r].l = mid + 1;
st[st[id].child_r].r = st[id].r;
}
if (l > mid) update(st[id].child_r , l , r);
else if (r <= mid) update(st[id].child_l , l , r);
else {
update(st[id].child_l , l , mid);
update(st[id].child_r , mid + 1 , r);
}
fix(st[id].child_l);
fix(st[id].child_r);
st[id].sum = st[st[id].child_l].sum + st[st[id].child_r].sum;
}
}
int get(int id , int l , int r){
fix(id);
if (st[id].l == l && st[id].r == r){
return st[id].sum;
}
else {
int mid = st[id].l + st[id].r >> 1;
if (st[id].child_l == -1){
st[id].child_l = node++;
st[st[id].child_l].l = st[id].l;
st[st[id].child_l].r = mid;
}
if (st[id].child_r == -1){
st[id].child_r = node++;
st[st[id].child_r].l = mid + 1;
st[st[id].child_r].r = st[id].r;
}
if (l > mid) return get(st[id].child_r , l , r);
else if (r <= mid) return get(st[id].child_l , l , r);
else {
return get(st[id].child_l , l , mid) + get(st[id].child_r , mid + 1 , r);
}
}
}
int32_t main (){
ios_base::sync_with_stdio(0);
cin.tie(0);
int m;
cin >> m;
int last = 0;
st[1].l = 1;
st[1].r = (int)1e9;
for ( int i = 1 ; i <= m ; i++ ){
int type , l , r;
cin >> type >> l >> r;
l += last;
r += last;
if (type == 1){
last = get(1 , l , r);
cout << last << el;
}
else update(1 , l , r);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |