제출 #1018369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1018369		AtinaR	Growing Trees (BOI11_grow)	C++14	0 / 100	195 ms	15972 KiB

grow

#include <bits/stdc++.h>

using namespace std;
const long long MAX=1e5+10;
long long niza[MAX],treemin[4*MAX],treemax[4*MAX],treeog[4*MAX];
long long lazy[4*MAX];
long long n,q;
void build(long long node, long long L, long long R)
{
    lazy[node]=0;
    if(L==R)
    {
        treemin[node]=niza[L];
        treemax[node]=niza[L];
        treeog[node]=niza[L];
        return;
    }
    long long mid=(L+R)/2;
    build(2*node,L,mid);
    build(2*node+1,mid+1,R);
    treemin[node]=min(treemin[2*node],treemin[2*node+1]);
    treemax[node]=max(treemax[2*node],treemax[2*node+1]);
    treeog[node]=treeog[2*node]+treeog[2*node+1];
}
void push(long long node, long long L, long long R)
{
    long long mid=(L+R)/2;
    if(lazy[node]==0)return;
    treemin[2*node]+=lazy[node];
    treemin[2*node+1]+=lazy[node];
    treemax[2*node]+=lazy[node];
    treemax[2*node+1]+=lazy[node];
    treeog[2*node]+=(mid-L+1);
    treeog[2*node+1]+=(R-mid);
    lazy[2*node]+=lazy[node];
    lazy[2*node+1]+=lazy[node];
    lazy[node]=0;
}
void update(long long node, long long L, long long R, long long _left, long long _right)
{
    if(L>=_left && R<=_right)
    {
        treemax[node]++;
        treemin[node]++;
        treeog[node]+=(R-L+1);
        lazy[node]++;
        return;
    }
    if(L>_right || R<_left)return;
    long long mid=(L+R)/2;
    push(node,L,R);
    update(2*node,L,mid,_left,_right);
    update(2*node+1,mid+1,R,_left,_right);
    treemax[node]=max(treemax[2*node],treemax[2*node+1]);
    treemin[node]=min(treemin[2*node],treemin[2*node+1]);

    treeog[node]=treeog[2*node]+treeog[2*node+1];
}

long long nobiggerthan(long long node, long long L, long long R, long long x)
{
    if(L==R)return L;
    push(node,L,R);
    long long mid=(L+R)/2;
    if(treemax[2*node+1]<=x)return nobiggerthan(2*node+1,mid+1,R,x);
    else if(treemax[2*node]<=x)return nobiggerthan(2*node,L,mid,x);
    else return 0;
}
long long firstatleast(long long node, long long L, long long R, long long x)
{
    if(L==R)
    {
        return L;
    }
    push(node,L,R);
    long long mid=(L+R)/2;
    if(treemax[2*node]>=x)return firstatleast(2*node,L,mid,x);
    else if(treemax[2*node+1]>=x) return firstatleast(2*node+1,mid+1,R,x);
    else return n;
}
long long getnum(long long node, long long L, long long R, long long x)
{
    if(L==R)
    {
        return treeog[node];
    }
    push(node,L,R);
    long long mid=(L+R)/2;
    if(x>mid)return getnum(2*node+1,mid+1,R,x);
    else return getnum(2*node,L,mid,x);
}
int main()
{
    cin>>n>>q;
    for(long long i=0; i<n; i++)cin>>niza[i];
    sort(niza,niza+n);
    build(1,0,n-1);
    for(long long i=0; i<q; i++)
    {
        char type;
        cin>>type;
        long long a,b;
        cin>>a>>b;
        if(type=='F')
        {
            long long l=firstatleast(1,0,n-1,b);
            if(l==n)continue;
            long long r=min(n-1,l+a-1);
            if(r==n-1)
            {
                update(1,0,n-1,l,n-1);
            }
            long long tmp=getnum(1,0,n-1,r);
            tmp--;

            long long lastfrom=nobiggerthan(1,0,n-1,tmp);
            update(1,0,n-1,l,lastfrom);
            long long too=nobiggerthan(1,0,n-1,tmp+1);
            long long howmanyleft=a-(lastfrom-l+1);
            long long newfrom=too-howmanyleft+1;
            update(1,0,n-1,newfrom,too);
        }
        else
        {
            long long l=firstatleast(1,0,n-1,a);
            long long r=nobiggerthan(1,0,n-1,b);
            cout<<r-l+1<<endl;
        }
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10