Submission #1041159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041159		ssense	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	350 ms	262144 KiB

apple

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>

#define fr first
#define sc second

using namespace std;

#define int long long

struct Tree
{
    int left, right;
    int sum = 0, lazy = 0;
    Tree *leftc = nullptr, *rightc = nullptr;
    Tree(int l, int r)
    {
        left = l; right = r;
    }
    void extend()
    {
        if(!leftc && left < right)
        {
            int mid = left+right>>1;
            leftc = new Tree(left, mid);
            rightc = new Tree(mid+1, right);
        }
    }
    void push()
    {
        extend();
        if(lazy == 1)
        {
            sum = right-left+1;
            if(leftc)
            {
                lazy = 0;
                leftc->lazy = 1;
                rightc->lazy = 1;
            }

        }
    }
    void add(int tl, int tr)
    {
        push();
        if(right < tl || left > tr)
        {
            return;
        }
        if(left >= tl && right <= tr)
        {
            lazy = 1;
            push();
            return;
        }
        leftc->add(tl, tr);
        rightc->add(tl, tr);
        sum = max(sum, leftc->sum+rightc->sum);
    }
    int get(int tl, int tr)
    {
        push();
        if(left > tr || right < tl)
        {
            return 0;
        }
        if(tl <= left && tr >= right)
        {
            return sum;
        }
        extend();
        return leftc->get(tl, tr)+rightc->get(tl, tr);
    }
};

void solve()
{
    int q;
    cin >> q;
    Tree base(1, 1000000000);
    int c = 0;
    while(q--)
    {
        int d, x, y;
        cin >> d >> x >> y;
        if(d == 1)
        {
            int ans = base.get(x+c, y+c);
            cout << ans << endl;
            c = ans;
        }
        else
        {
            base.add(x+c, y+c);
        }
    }
}

int32_t main()
{
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}
/*
6
2 1 7
2 10 12
1 7 11
2 11 13
1 8 10
1 15 17
*/
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/

Compilation message (stderr)

apple.cpp: In member function 'void Tree::extend()':
apple.cpp:41:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |             int mid = left+right>>1;
      |                       ~~~~^~~~~~

• Subtask 1: 0 / 100