Submission #1276555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276555		eldarr	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	303 ms	130504 KiB

apple

#include <bits/stdc++.h>
#define ll long long
#define dl double
#define str string
#define tst to_string
#define pb push_back
#define pf push_front
#define eb emplace_back
#define u_b upper_bound
#define l_b lower_bound
#define ff first
#define ss second
#define INF 1000000001
#define mxn 100001
#define mod 1000000007
#define come_on ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
const int sz=1e5+5;
const int trs=1e7+5;
struct node{
    int lchild,rchild,res,lz;
};
int last=1;
node st[trs];
void extend(int ind)
{
    if(st[ind].lchild) return;
    st[ind].lchild=++last;
    st[ind].rchild=++last;
}
void relax(int l,int r,int in)
{
    if(!st[in].lz)
    {
        return;
    }
    st[in].res=r-l+1;
    if(l!=r)
    {
        extend(in);
        st[st[in].lchild].lz=st[st[in].rchild].lz=1;
    }
    st[in].lz=0;
}
void update(int a,int b,int l,int r,int in)
{
    relax(l,r,in);
    if(b<l || r<a)
    {
        return;
    }
    if(a<=l and r<=b)
    {
        st[in].lz=1;
        relax(l,r,in);
        return;
    }
    int mid=(l+r)>>1;
    extend(in);
    update(a,b,l,mid,st[in].lchild);
    update(a,b,mid+1,r,st[in].rchild);
    st[in].res=st[st[in].lchild].res+st[st[in].rchild].res;
}
ll getans(int a,int b,int l,int r,int in)
{
    relax(l,r,in);
    if(b<l or r<a)
    {
        return 0;
    }
    if(a<=l and r<=b)
    {
        return st[in].res;
    }
    int mid=(l+r)>>1;
    return getans(a,b,l,mid,st[in].lchild)+getans(a,b,mid+1,r,st[in].rchild);
}
void solve()
{
    int q;
    cin>>q;
    int c=0;
    int n=1e9+5;
    while(q--)
    {
        int t,l,r;
        cin>>t>>l>>r;
        l+=c;
        r+=c;
        if(t==1)
        {
            c=getans(l,r,1,n,1);
            cout<<c<<'\n';
        }
        else
        {
            update(l,r,1,n,1);
        }
        
        
    }
}
int main()
{
    int T=1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
}

• Subtask 1: 100 / 100