Submission #876774

#	Time	Username	Problem	Language	Result	Execution time	Memory
876774		presko	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	162 ms	262144 KiB

apple

#include<iostream>
#include<bits/stdc++.h>
#define MAXN 4000010
#define BIL 1000000010
using namespace std;
struct node
{
    int l,r;
    int sum,lazy;

    void newNode()
    {
        sum=0;
        lazy=0;
        l=-1;
        r=-1;
    }
};
int len=1;
node tree[MAXN];
void update(int ind, int l, int r, int ql, int qr)
{
    if(ql<0 || qr<0)return;
    if(ql<=l && r<=qr)
    {
        tree[ind].lazy=1;
        return;
    }
    int mid=(l+r)/2;
    if(ql<=mid)
    {
        if(tree[ind].l==-1)
        {
            len++;
            tree[len].newNode();
            tree[ind].l=len;
        }
        update(tree[ind].l,l,mid,ql,qr);
    }
    if(qr>mid)
    {
        if(tree[ind].r==-1)
        {
            len++;
            tree[len].newNode();
            tree[ind].r=len;
        }
        update(tree[ind].r,mid+1,r,ql,qr);
    }
    //tree[ind].lazy=(tree[tree[ind].l].lazy && tree[tree[ind].r].lazy);
}
int query(int ind, int l, int r, int ql, int qr, int up)
{
    if(r<ql || l>qr || ql<0 || qr<0)return 0;
    //cout<<ind<<"i "<<l<<" "<<r<<" "<<tree[ind].lazy<<"\n";
    if(ql<=l && r<=qr && tree[ind].lazy==1)return r-l+1;
    int mid=(l+r)/2;
    int val1=0,val2=0;
    if(ql<=mid)
    {
        if(tree[ind].l!=-1)val1= query(tree[ind].l,l,mid,ql,qr,up);
        else if(tree[ind].lazy==1)
        {
            tree[tree[ind].l].lazy=1;
            val1= query(tree[ind].l,l,mid,ql,qr,up);
        }
    }
    if(qr>mid)
    {
        if(tree[ind].r!=-1)val2= query(tree[ind].r,mid+1,r,ql,qr,up);
        else if(tree[ind].lazy==1)
        {
            tree[tree[ind].r].lazy=1;
            val2= query(tree[ind].r,mid+1,r,ql,qr,up);
        }
    }
    //cout<<ind<<"i "<<val1<<" "<<val2<<"\n";
    return val1+val2;
}
int main()
{
    int n,c=0;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    tree[1].newNode();
    /*if(tree[1].l==-1)
    {
        tree[2].newNode(tree[1].lv,tree[1].rv/2);
        tree[1].l=2;
    }*/
    for(int i=0;i<n;i++)
    {
        int d,x,y;
        cin>>d>>x>>y;
        if(d==2)
        {
            update(1,1,BIL,x+c,y+c);
        }
        else
        {
            int res=query(1,1,BIL,x+c,y+c,0);
            c=res;
            cout<<res<<"\n";
        }
    }
}

Compilation message (stderr)

apple.cpp: In function 'int query(int, int, int, int, int, int)':
apple.cpp:64:29: warning: array subscript -1 is below array bounds of 'node [4000010]' [-Warray-bounds]
   64 |             tree[tree[ind].l].lazy=1;
      |             ~~~~~~~~~~~~~~~~^
apple.cpp:20:6: note: while referencing 'tree'
   20 | node tree[MAXN];
      |      ^~~~
apple.cpp:73:29: warning: array subscript -1 is below array bounds of 'node [4000010]' [-Warray-bounds]
   73 |             tree[tree[ind].r].lazy=1;
      |             ~~~~~~~~~~~~~~~~^
apple.cpp:20:6: note: while referencing 'tree'
   20 | node tree[MAXN];
      |      ^~~~

• Subtask 1: 0 / 100