Submission #593549

#TimeUsernameProblemLanguageResultExecution timeMemory
593549no_nameeMonkey and Apple-trees (IZhO12_apple)C++14
100 / 100
388 ms137920 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;
const int maxn = 1e9;
struct node
{
    bool lazy;
    int sum;
    node *left, *right;
    node ()
    {
        lazy = sum = false;
        left = right = nullptr;
    }
};
void update( node *ptr, int left , int right, int u,  int v )
{
    if(  left > v || right < u )return;

    if( left >= u && right <= v )
    {
        ptr->sum =  right - left + 1;
        ptr->lazy = true;
        return;
    }

    int mid = ( ( left + right )>>1);
    if( ptr->left  == nullptr ) ptr->left  = new(node);
    if( ptr->right == nullptr ) ptr->right = new(node);
    if( ptr->lazy )
    {
        ptr->left->lazy = ptr->right->lazy = true;
        ptr->left->sum  = mid -  left + 1;
        ptr->right->sum = right - mid;
        ptr->lazy = false;
    }
    update(ptr->left,left,mid,u,v);
    update(ptr->right,mid+1,right,u,v);
    ptr->sum =  ptr->left->sum + ptr->right->sum;
}
int query( node *ptr, int left , int right, int u,  int v )
{
    if(  left > v || right < u )return 0 ;
    if( left >= u && right <= v ) return ptr->sum;

    int mid = ( ( left + right )>>1);

    if( ptr->left  == nullptr ) ptr->left  = new(node);
    if( ptr->right == nullptr ) ptr->right = new(node);
    if( ptr->lazy )
    {
        ptr->left->lazy = ptr->right->lazy = true;
        ptr->left->sum  = mid -  left + 1;
        ptr->right->sum = right - mid;
        ptr->lazy = false;
    }
    return ( query( ptr->left, left, mid,u,v) + query( ptr->right, mid+1,right, u,v) );
}
node *root;
void solve()
{
    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);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Compilation message (stderr)

apple.cpp: In constructor 'node::node()':
apple.cpp:22:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   22 |         lazy = sum = false;
      |                ~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...