제출 #1277539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277539		k12_khoi	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	193 ms	66792 KiB

apple

#include <bits/stdc++.h>
using namespace std;

int n,request,timer,type,u,v,res;
vector <int> t,Left,Right;

void addLeftRight(int id)
{
    if (!Left[id])
    {
        Left[id]=++timer;
        t.emplace_back();
        Left.emplace_back();
        Right.emplace_back();
    }
    if (!Right[id])
    {
        Right[id]=++timer;
        t.emplace_back();
        Left.emplace_back();
        Right.emplace_back();
    }
}

void down(int id,int l,int r)
{
    if (t[id]==r-l+1)
    {
        int m=(l+r)/2;
        t[Left[id]]=m-l+1;
        t[Right[id]]=r-m;
    }
}

void update(int id,int l,int r)
{
    if (u>r or v<l) return;
    if (u<=l and v>=r)
    {
        t[id]=r-l+1;
        return;
    }
    addLeftRight(id);

    down(id,l,r);
    int m=(l+r)/2;

    update(Left[id],l,m);
    update(Right[id],m+1,r);

    t[id]=t[Left[id]]+t[Right[id]];
}

int get(int id,int l,int r)
{
    if (u>r or v<l) return 0;
    if (u<=l and v>=r) return t[id];

    addLeftRight(id);

    down(id,l,r);
    int m=(l+r)/2;
    return get(Left[id],l,m)+get(Right[id],m+1,r);
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    n=1e9;
    timer=0;
    t.emplace_back();
    Left.emplace_back();
    Right.emplace_back();


    res=0;
    cin >> request;
    while (request--)
    {
        cin >> type >> u >> v;
        u+=res;
        v+=res;

        if (type==1)
        {
            res=get(0,1,n);
            cout << res << '\n';
        }
        else update(0,1,n);
    }
}

• Subtask 1: 100 / 100