Submission #957928

# Submission time Handle Problem Language Result Execution time Memory
957928 2024-04-04T13:41:43 Z bmh123456789asdf Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
68 ms 75764 KB
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
using namespace std;
const int N = 12345;



struct Node {
    int sum, lazy, tl, tr, l, r;
    Node() : sum(0), lazy(0), l(-1), r(-1) {}
};
Node tree[64 * N];
int cnt = 2;

void pushlazy(int id)
{
    if(tree[id].lazy)
    {
        tree[id].sum = tree[id].tr - tree[id].tl + 1;
        int mid = (tree[id].tr + tree[id].tl) / 2;
        if(tree[id].l == -1)
        {
            tree[id].l = ++cnt;
            tree[cnt].tl = tree[id].tl;
            tree[cnt].tr = mid;
        }
        if(tree[id].r == -1)
        {
            tree[id].r = ++cnt;
            tree[cnt].tl = mid + 1;
            tree[cnt].tr = tree[id].tr;
        }
        tree[tree[id].l].lazy = tree[tree[id].r].lazy = 1;
        tree[id].lazy = 0;
    }
}

void update(int id,int low,int high)
{
    pushlazy(id);
    if(low == tree[id].tl && high == tree[id].tr)
    {
        tree[id].lazy = 1;
        pushlazy(id);
    }
    else
    {
        int mid = (tree[id].tr + tree[id].tl) / 2;
        if(tree[id].l == -1)
        {
            tree[id].l = ++cnt;
            tree[cnt].tl = tree[id].tl;
            tree[cnt].tr = mid;
        }
        if(tree[id].r == -1)
        {
            tree[id].r = ++cnt;
            tree[cnt].tl = mid + 1;
            tree[cnt].tr = tree[id].tr;
        }

        if(low > mid) update(tree[id].r, low, high);
        else if(high <= mid) update(tree[id].l, low, high);
        else
        {
            update(tree[id].l, low, mid);
            update(tree[id].r, mid + 1, high);
        }
        pushlazy(tree[id].l);
        pushlazy(tree[id].r);

        tree[id].sum = tree[tree[id].l].sum + tree[tree[id].r].sum;
    }
}

int query(int id,int low,int high)
{
    pushlazy(id);
    if(low == tree[id].tl && high == tree[id].tr) return tree[id].sum;
    else
    {
        int mid = (tree[id].tr + tree[id].tl) / 2;
        if(tree[id].l == -1)
        {
            tree[id].l = ++cnt;
            tree[cnt].tl = tree[id].tl;
            tree[cnt].tr = mid;
        }
        if(tree[id].r == -1)
        {
            tree[id].r = ++cnt;
            tree[cnt].tl = mid + 1;
            tree[cnt].tr = tree[id].tr;
        }

        if(low > mid) return query(tree[id].r, low, high);
        else if(high <= mid) return query(tree[id].l, low, high);
        else return query(tree[id].l, low, mid) + query(tree[id].r, mid + 1, high);
    }
}


int32_t main()
{
//    freopen("f.in", "r" ,stdin);
//    freopen("f.out", "w" ,stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int m, d, x, y, c = 0;

    tree[1].sum = 0;
	tree[1].lazy = 0;
	tree[1].tl = 1;
	tree[1].tr = 1e9;

    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> d >> x >> y;
        if(d == 1)
        {
            c = query(1, x + c, y + c);
            cout << c <<'\n';
        }
        else update(1, x + c, y + c);

    }
}
# Verdict Execution time Memory Grader output
1 Correct 7 ms 37468 KB Output is correct
2 Correct 7 ms 37468 KB Output is correct
3 Correct 6 ms 37468 KB Output is correct
4 Correct 16 ms 37468 KB Output is correct
5 Correct 16 ms 37468 KB Output is correct
6 Correct 16 ms 37512 KB Output is correct
7 Correct 16 ms 37468 KB Output is correct
8 Runtime error 68 ms 75764 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -