Submission #1041163

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1041163	2024-08-01T16:22:37 Z	ssense	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	318 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()
    {
        if(lazy == 1)
        {
            extend();
            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;
        }
        extend();
        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(0, 1000000005);
    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	0 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	25 ms	8536 KB	Output is correct
5	Correct	19 ms	10332 KB	Output is correct
6	Correct	19 ms	10020 KB	Output is correct
7	Correct	20 ms	10332 KB	Output is correct
8	Correct	139 ms	77020 KB	Output is correct
9	Correct	308 ms	130896 KB	Output is correct
10	Correct	313 ms	147120 KB	Output is correct
11	Correct	308 ms	159312 KB	Output is correct
12	Correct	318 ms	164948 KB	Output is correct
13	Correct	297 ms	207136 KB	Output is correct
14	Correct	311 ms	209308 KB	Output is correct
15	Runtime error	313 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-