Submission #1041159

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1041159	2024-08-01T16:18:27 Z	ssense	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	350 ms	262144 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	16 ms	11356 KB	Output is correct
5	Correct	20 ms	13904 KB	Output is correct
6	Correct	21 ms	13400 KB	Output is correct
7	Correct	22 ms	13912 KB	Output is correct
8	Correct	166 ms	103516 KB	Output is correct
9	Correct	323 ms	175952 KB	Output is correct
10	Correct	332 ms	197460 KB	Output is correct
11	Correct	337 ms	214060 KB	Output is correct
12	Correct	350 ms	221536 KB	Output is correct
13	Runtime error	343 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-