답안 #1041162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041162	2024-08-01T16:21:53 Z	ssense	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	360 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

#	결과	실행 시간	메모리	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	17 ms	11384 KB	Output is correct
5	Correct	22 ms	13660 KB	Output is correct
6	Correct	20 ms	13148 KB	Output is correct
7	Correct	24 ms	13660 KB	Output is correct
8	Correct	156 ms	102516 KB	Output is correct
9	Correct	326 ms	174420 KB	Output is correct
10	Correct	328 ms	195704 KB	Output is correct
11	Correct	360 ms	212304 KB	Output is correct
12	Correct	338 ms	219440 KB	Output is correct
13	Runtime error	332 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-