Submission #585969

# Submission time Handle Problem Language Result Execution time Memory
585969 2022-06-29T15:44:41 Z MohamedAliSaidane Monkey and Apple-trees (IZhO12_apple) C++14
100 / 100
373 ms 188496 KB
#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();
        }



# Verdict Execution time Memory Grader output
1 Correct 86 ms 185804 KB Output is correct
2 Correct 77 ms 185844 KB Output is correct
3 Correct 77 ms 185804 KB Output is correct
4 Correct 83 ms 185776 KB Output is correct
5 Correct 86 ms 185864 KB Output is correct
6 Correct 96 ms 185812 KB Output is correct
7 Correct 92 ms 185932 KB Output is correct
8 Correct 169 ms 185928 KB Output is correct
9 Correct 312 ms 186236 KB Output is correct
10 Correct 320 ms 186228 KB Output is correct
11 Correct 313 ms 186240 KB Output is correct
12 Correct 314 ms 186276 KB Output is correct
13 Correct 267 ms 186336 KB Output is correct
14 Correct 271 ms 186444 KB Output is correct
15 Correct 367 ms 188460 KB Output is correct
16 Correct 361 ms 188496 KB Output is correct
17 Correct 275 ms 188384 KB Output is correct
18 Correct 278 ms 188400 KB Output is correct
19 Correct 364 ms 188428 KB Output is correct
20 Correct 373 ms 188492 KB Output is correct