제출 #593515

#제출 시각아이디문제언어결과실행 시간메모리
593515no_namee원숭이와 사과 나무 (IZhO12_apple)C++14
0 / 100
0 ms212 KiB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define lli long long int
#define ulli unsigned long long int
#define ld long double
using namespace std;
using namespace __gnu_pbds;
struct node
{
    node *left,*right;
    lli val, lazy;
    node ()
    {
        left = right = nullptr;
        val = lazy = 0;
    }
};
const int maxn = 1e9;
node * root = nullptr ;
inline void down( node * ptr , int left, int mid , int right )
{
    if( ptr->left  == nullptr ) ptr->left  = new(node);
    if( ptr->right == nullptr ) ptr->right = new(node);
    ptr->left->lazy = ptr->right->lazy = 1;
    ptr->left->val = mid - left + 1;
    ptr->right->val = right - mid + 1;
    ptr->val = right - left + 1 ;
    ptr->lazy = 0;
}
void update( node *ptr , int left  , int right , int u, int v )
{
    if( left >= u && right <= v )
    {
        ptr->val  = ( right - left +  1);
        ptr->lazy = 1;
//        cout <<" vao if left = "<< left <<" right = "<< right <<" val = "<< ptr->val <<endl;
        return;
    }
    int mid = ( ( left + right) >> 1 );
    if( ptr->lazy == 1 )
    {
        down(ptr,left,mid,right);
        return;
    }
//    cout <<" pre ans left = "<< left <<" right = "<< right <<" ans = "<< ptr->val <<endl;
    ptr->val = 0;
    if( !( left > v || mid < u ) )
    {
        if( ptr->left == nullptr ) ptr->left =  new(node);
        update(ptr->left,left,mid,u,v);
        ptr->val +=  ptr->left->val;
    }
    if( !( mid+1 > v || right < u ) )
    {
        if( ptr->right == nullptr ) ptr->right =  new(node);
        update(ptr->right,mid+1,right,u,v);
        ptr->val +=  ptr->right->val;
    }
//    cout <<" left  = "<< left <<" right = "<< right << " val = "<< ptr->val <<endl;
}
int query ( node * ptr , int left , int right , int u, int v )
{
    if( left > v || right < u )return 0;
    if( ptr == nullptr ) ptr = new(node);

    if( left >= u && right <= v ) return ptr->val;

    int mid = ( (left + right)>>1);
    if( ptr->lazy == 1) down(ptr,left,mid,right);
    return ( query( ptr->left,left, mid,u,v) + query( ptr->right, mid+1,right,u,v)  );
}
void read()
{
	int q, type, x,y,c =  0, ans;
	cin >> q;
	root = new(node);
	while(q--)
    {
        cin >> type >> x >> y;
        x += c;
        y += c;
        if( type == 1 )
        {
            ans = query(root,1,maxn,x,y);
            c = ans;
            cout << ans<< '\n';
        }
        else
        {
            update(root,1,maxn,x,y);
        }
//        cout <<" root.val  = "<< root->val <<endl;
//        cout <<endl<<"_____________________________________________"<<endl;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...