Submission #593549

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
593549	2022-07-11T11:27:31 Z	no_namee	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	388 ms	137920 KB

apple

#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

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	10 ms	3412 KB	Output is correct
5	Correct	13 ms	4124 KB	Output is correct
6	Correct	12 ms	4000 KB	Output is correct
7	Correct	12 ms	4104 KB	Output is correct
8	Correct	95 ms	29864 KB	Output is correct
9	Correct	196 ms	51368 KB	Output is correct
10	Correct	208 ms	56632 KB	Output is correct
11	Correct	221 ms	60752 KB	Output is correct
12	Correct	220 ms	62612 KB	Output is correct
13	Correct	196 ms	72788 KB	Output is correct
14	Correct	188 ms	73548 KB	Output is correct
15	Correct	301 ms	133968 KB	Output is correct
16	Correct	388 ms	134876 KB	Output is correct
17	Correct	189 ms	76068 KB	Output is correct
18	Correct	199 ms	76080 KB	Output is correct
19	Correct	347 ms	137916 KB	Output is correct
20	Correct	323 ms	137920 KB	Output is correct