Submission #585969

#	Time	Username	Problem	Language	Result	Execution time	Memory
585969		MohamedAliSaidane	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	373 ms	188496 KiB

apple

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace __gnu_pbds;
        using namespace std;

        typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;

        typedef long long ll;
        typedef long double ld;

        //#define int ll

        typedef pair<int,int> pii;
        typedef pair<ll,ll> pll;
        typedef pair<ld,ld> pld;

        typedef vector<int> vi;
        typedef vector<ll> vll;
        typedef vector<pii> vpi;
        typedef vector<pll> vpl;

        #define pb push_back
        #define popb pop_back
        #define pp pop_back
        #define pf push_front
        #define popf pop_front
        #define all(x) (x).begin(),(x).end()
        #define ff first
        #define ss second



        int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
        ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
        ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}

        struct Node
        {
            int sum, lazy, tl, tr, l, r;
            Node(): sum(0), lazy(0), l(-1), r(-1) {}
        };
        const int nax = 123456;
        Node segtree[64 * nax];
        int cnt = 2;
        void propagate(int node)
        {
            if(segtree[node].lazy)
            {
                segtree[node].sum = (segtree[node].tr - segtree[node].tl + 1ll);
                if(segtree[node].tl != segtree[node].tr)
                {
                    int m = (segtree[node].tl + segtree[node].tr)/2;
                    if(segtree[node].l == -1)
                    {
                        segtree[node].l = cnt ++;
                        segtree[segtree[node].l].tl = segtree[node].tl;
                        segtree[segtree[node].l].tr = m;
                    }
                    if(segtree[node].r == -1)
                    {
                        segtree[node].r = cnt ++;
                        segtree[segtree[node].r].tl = m + 1;
                        segtree[segtree[node].r].tr = segtree[node].tr;
                    }
                    segtree[segtree[node].l].lazy = 1;
                    segtree[segtree[node].r].lazy = 1;
                }
                segtree[node].lazy = 0;
            }
        }
        void update(int node, int l, int r)
        {
            propagate(node);
            if(l > r)
                return;
            if(segtree[node].tl ==  l && segtree[node].tr == r)
            {
                segtree[node].lazy = 1 ;
                propagate(node);
            }
            else
            {
                int m = (segtree[node].tl + segtree[node].tr)/2;
                if(segtree[node].l == -1)
                {
                    segtree[node].l = cnt ++;
                    segtree[segtree[node].l].tl = segtree[node].tl;
                    segtree[segtree[node].l].tr = m;
                }
                if(segtree[node].r == -1)
                {
                    segtree[node].r = cnt ++;
                    segtree[segtree[node].r].tl = m + 1;
                    segtree[segtree[node].r].tr = segtree[node].tr;
                }
                if(l > m)
                    update(segtree[node].r, l, r);
                else if(r <=m)
                    update(segtree[node].l, l, r);
                else
                {
                    update(segtree[node].l, l, m);
                    update(segtree[node].r, m + 1, r);
                }
                propagate(segtree[node].l);
                propagate(segtree[node].r);
                segtree[node].sum = segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
            }
        }
        int query(int node, int l, int r)
        {
            propagate(node);
            if(l == segtree[node].tl && r == segtree[node].tr)
                return segtree[node].sum;
            else
            {
                int m = (segtree[node].tl + segtree[node].tr)/2;
                if(segtree[node].l == -1)
                {
                    segtree[node].l = cnt ++;
                    segtree[segtree[node].l].tl = segtree[node].tl;
                    segtree[segtree[node].l].tr = m;
                }
                if(segtree[node].r == -1)
                {
                    segtree[node].r = cnt ++;
                    segtree[segtree[node].r].tl = m + 1;
                    segtree[segtree[node].r].tr = segtree[node].tr;
                }
                if(l > m)
                    return query(segtree[node].r, l, r);
                else if(r<= m)
                    return query(segtree[node].l, l, r);
                else
                {
                    return query(segtree[node].l,l,m) + query(segtree[node].r,m + 1,r);
                }

            }

        }
        void solve()
        {
            segtree[1].tl = 1;
            segtree[1].tr = 1e9;
            segtree[1].sum = 0;
            int m; cin >> m;
            int c = 0;
            for(int i = 1; i <= m ; i++)
            {
                int d, x, y;
                cin >> d >> x >> y;
                if(d == 1)
                {
                    c = query(1,x + c,y + c);
                    cout << c << '\n';
                }
                else
                {
                    update(1,x + c,y + c);
                }
            }

        }

        int32_t main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0); cout.tie(0);
            int tt = 1;//cin >> tt;
            while(tt --)
                solve();
        }

• Subtask 1: 100 / 100