제출 #1309570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309570		fatuu27	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	185 ms	64268 KiB

apple

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int m,n=1e9,c;
int fs[5000005],fd[5000005],aint[5000005],idx;
bool lazy[5000005];
void create_sons(int x)
{
    if(!fs[x]) fs[x]=++idx;
    if(!fd[x]) fd[x]=++idx;
}
void propagate(int node,int st,int dr)
{
    if(!lazy[node])
        return;
    aint[node]=dr-st+1;
    if(st==dr)
    {
        lazy[node]=0;
        return;
    }
    lazy[fs[node]]=lazy[node];
    lazy[fd[node]]=lazy[node];
    lazy[node]=0;
}
void update(int node,int st,int dr,int x,int y)
{
    create_sons(node);
    propagate(node,st,dr);
    if(st>=x && dr<=y)
    {
        lazy[node]=1;
        propagate(node,st,dr);
        return;
    }
    if(st>y || dr<x)
        return;
    int mij=(st+dr)>>1;
    update(fs[node],st,mij,x,y);
    update(fd[node],mij+1,dr,x,y);
    aint[node]=aint[fs[node]]+aint[fd[node]];
}
int query(int node,int st,int dr,int x,int y)
{
    create_sons(node);
    propagate(node,st,dr);
    if(st>=x && dr<=y)
    {
        return aint[node];
    }
    if(st>y || dr<x)
        return 0;
    int mij=(st+dr)>>1;
    return query(fs[node],st,mij,x,y)+query(fd[node],mij+1,dr,x,y);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>m;
    idx++;
    while(m--)
    {
        int op,x,y;
        cin>>op>>x>>y;
        x+=c;
        y+=c;
        if(op==2)
        {
            update(1,1,n,x,y);
        }
        else
        {
            c=query(1,1,n,x,y);
            cout<<c<<"\n";
        }
    }
    return 0;
}

• Subtask 1: 0 / 100