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
#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;
}
# 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