제출 #885945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
885945		heeheeheehaaw	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	3 ms	3804 KiB

apple

#include <vector>
#include <iostream>
#pragma GCC optimize("O3,unroll-loops")

using namespace std;

struct node
{
    short int sum, lazy;
    short int nl, nr;
};

vector<node> aint;
const int lim = 1000000000;

void propagate(int nod, int st, int dr)
{
    if(aint[nod].lazy == 0)
        return;

    int mij = (st + dr) / 2;
    aint[aint[nod].nl].sum += (mij - st + 1) * aint[nod].lazy;
    aint[aint[nod].nr].sum += (dr - mij) * aint[nod].lazy;
    aint[aint[nod].nl].lazy = 1;
    aint[aint[nod].nr].lazy = 1;
    aint[nod].lazy = 0;
    return;
}

void update(int nod, int st, int dr, int le, int ri)
{
    if(le > ri)
        return;

    if(st == le && dr == ri)
    {
        aint[nod].sum = dr - st + 1;
        aint[nod].lazy = 1;
        return;
    }

    if(aint[nod].nl == -1)
    {
        aint[nod].nl = aint.size();
        aint.push_back({0, 0, -1, -1});
    }

    if(aint[nod].nr == -1)
    {
        aint[nod].nr = aint.size();
        aint.push_back({0, 0, -1, -1});
    }

    propagate(nod, st, dr);

    int mij = (st + dr) / 2;
    update(aint[nod].nl, st, mij, le, min(ri, mij));
    update(aint[nod].nr, mij + 1, dr, max(le, mij + 1), ri);
    aint[nod].sum = aint[aint[nod].nl].sum + aint[aint[nod].nr].sum;
}

int query(int nod, int st, int dr, int le, int ri)
{
    if(le > ri)
        return 0;
    if(st == le && dr == ri)
        return aint[nod].sum;

    if(aint[nod].nl == -1)
    {
        aint[nod].nl = aint.size();
        aint.push_back({0, 0, -1, -1});
    }

    if(aint[nod].nr == -1)
    {
        aint[nod].nr = aint.size();
        aint.push_back({0, 0, -1, -1});
    }

    propagate(nod, st, dr);
    int mij = (st + dr) / 2;
    return query(aint[nod].nl, st, mij, le, min(ri, mij)) +
           query(aint[nod].nr, mij + 1, dr, max(le, mij + 1), ri);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    aint.push_back({0, 0, -1, -1});
    int m, c = 0;
    cin>>m;
    for(int i = 1; i <= m; i++)
    {
        int t, x, y;
        cin>>t>>x>>y;
        x += c;
        y += c;

        if(t == 1)
        {
            c = query(0, 1, lim, x, y);
            cout<<c<<'\n';

        }
        else
        {
            update(0, 1, lim, x, y);
        }
    }
    return 0;
}

• Subtask 1: 0 / 100