Submission #877062

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
877062	2023-11-22T20:06:58 Z	presko	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	142 ms	52396 KB

apple

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

    void newNode()
    {
        lazy=0; sum=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<=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].sum=0;
    if (tree[ind].l!=-1) {
        if (tree[tree[ind].l].lazy==1) tree[ind].sum+=(mid-l+1);
        else tree[ind].sum+=tree[tree[ind].l].sum;
    }
    if (tree[ind].r!=-1) {
        if (tree[tree[ind].r].lazy==1) tree[ind].sum+=(r-(mid+1)+1);
        else tree[ind].sum+=tree[tree[ind].r].sum;
    }
}
int query(int ind, int l, int r, int ql, int qr, bool up)
{
    up|=tree[ind].lazy;
    if(ql<=l && r<=qr){
        if (up==true) return (r-l+1);
        return tree[ind].sum;
    }
    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(up>0)
        {
            len++;
            tree[len].newNode();
            tree[ind].l=len;
            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(up>0)
        {
            len++;
            tree[len].newNode();
            tree[ind].r=len;
            val2= query(tree[ind].r,mid+1,r,ql,qr,up);
        }
    }
    return val1+val2;
}
int main()
{
    int n,c=0;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    tree[1].newNode();
    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";
        }
    }
}

Subtask #1

100.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	Correct	0 ms	344 KB	Output is correct
4	Correct	6 ms	2652 KB	Output is correct
5	Correct	8 ms	2652 KB	Output is correct
6	Correct	8 ms	2648 KB	Output is correct
7	Correct	8 ms	2648 KB	Output is correct
8	Correct	48 ms	13052 KB	Output is correct
9	Correct	102 ms	21444 KB	Output is correct
10	Correct	107 ms	23384 KB	Output is correct
11	Correct	135 ms	23580 KB	Output is correct
12	Correct	98 ms	25600 KB	Output is correct
13	Correct	93 ms	29780 KB	Output is correct
14	Correct	97 ms	29796 KB	Output is correct
15	Correct	139 ms	52348 KB	Output is correct
16	Correct	130 ms	52304 KB	Output is correct
17	Correct	112 ms	29776 KB	Output is correct
18	Correct	93 ms	29780 KB	Output is correct
19	Correct	142 ms	52396 KB	Output is correct
20	Correct	134 ms	52240 KB	Output is correct