Submission #1041170

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1041170	2024-08-01T16:38:47 Z	ssense	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	438 ms	255344 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;
                leftc->sum = leftc->right-leftc->left+1;
                rightc->sum = rightc->right-rightc->left+1;
            }

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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	15 ms	5980 KB	Output is correct
5	Correct	18 ms	7296 KB	Output is correct
6	Correct	18 ms	7004 KB	Output is correct
7	Correct	17 ms	7260 KB	Output is correct
8	Correct	132 ms	53308 KB	Output is correct
9	Correct	271 ms	92240 KB	Output is correct
10	Correct	260 ms	102268 KB	Output is correct
11	Correct	276 ms	110160 KB	Output is correct
12	Correct	273 ms	113576 KB	Output is correct
13	Correct	252 ms	134116 KB	Output is correct
14	Correct	272 ms	135764 KB	Output is correct
15	Correct	377 ms	248180 KB	Output is correct
16	Correct	387 ms	249680 KB	Output is correct
17	Correct	253 ms	141396 KB	Output is correct
18	Correct	261 ms	141440 KB	Output is correct
19	Correct	377 ms	255312 KB	Output is correct
20	Correct	438 ms	255344 KB	Output is correct