Submission #885951

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885951	2023-12-11T07:53:13 Z	heeheeheehaaw	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	166 ms	134308 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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	7 ms	2520 KB	Output is correct
5	Correct	9 ms	2520 KB	Output is correct
6	Correct	9 ms	2520 KB	Output is correct
7	Correct	9 ms	2520 KB	Output is correct
8	Correct	49 ms	17848 KB	Output is correct
9	Correct	118 ms	34736 KB	Output is correct
10	Correct	110 ms	35260 KB	Output is correct
11	Correct	112 ms	34480 KB	Output is correct
12	Correct	114 ms	33972 KB	Output is correct
13	Correct	112 ms	67824 KB	Output is correct
14	Correct	109 ms	66480 KB	Output is correct
15	Correct	166 ms	132372 KB	Output is correct
16	Correct	162 ms	134308 KB	Output is correct
17	Correct	124 ms	68576 KB	Output is correct
18	Correct	119 ms	67528 KB	Output is correct
19	Correct	160 ms	133964 KB	Output is correct
20	Correct	160 ms	133532 KB	Output is correct