oj.uz

Submission #1018371

# Submission time Handle Problem Language Result Execution time Memory
1018371 2024-07-09T20:45:26 Z AtinaR Growing Trees (BOI11_grow) C++14
0 / 100
 171 ms 14052 KB 
#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]+=lazy[node]*(mid-L+1);
    treeog[2*node+1]+=lazy[node]*(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.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 13648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 8880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 9040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 11352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 13400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 13596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 13648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 13616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 14052 KB Output isn't correct
2 Halted 0 ms 0 KB -