Submission #885948

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885948	2023-12-11T07:50:43 Z	heeheeheehaaw	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	176 ms	262144 KB

apple

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

using namespace std;

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

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

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[aint[nod].nr].sum += (dr - mij);
    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.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	Runtime error	176 ms	262144 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-