oj.uz

Submission #877050

# Submission time Handle Problem Language Result Execution time Memory
877050 2023-11-22T19:43:41 Z iliyan98 Monkey and Apple-trees (IZhO12_apple) C++17
0 / 100
 0 ms 348 KB 
#include<iostream>
#include<bits/stdc++.h>
#define MAXN 4000010
#define BIL 1000000010
using namespace std;
struct node
{
    int l,r;
    int 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++;
        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) tree[ind].sum+=tree[tree[ind].l].sum+tree[tree[ind].l].lazy*(mid-l+1);
    if (tree[ind].r!=-1) tree[ind].sum+=tree[tree[ind].r].sum+tree[tree[ind].r].lazy*(r-(mid+1)+1);
}
int query(int ind, int l, int r, int ql, int qr, int up)
{
    up+=tree[ind].lazy;
    if(ql<=l && r<=qr)return tree[ind].sum+(r-l+1)*1LL*up;
    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";
        }
    }
}
/*
3
2 5 8
2 7 10
1 1 10

4
2 2 3
1 1 3
2 2 3
1 -1 3

6
2 1 7
2 10 12
1 7 11
2 11 13
1 8 10
1 15 17

3
2 1 8
2 13 18
1 6 15
*/

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -