oj.uz

Submission #1023592

# Submission time Handle Problem Language Result Execution time Memory
1023592 2024-07-15T03:24:54 Z AtinaR Growing Trees (BOI11_grow) C++14
0 / 100
 193 ms 6740 KB 
#include <bits/stdc++.h>

using namespace std;
const int MAX=1e5+10;
int n,q;
int niza[MAX];
int treemin[4*MAX],treemax[4*MAX],lazy[4*MAX];
void build(int node, int L, int R)
{
    lazy[node]=0;
    if(L==R)
    {
        treemin[node]=niza[L];
        treemax[node]=niza[L];
        return;
    }
    int 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]);
}
void push(int node, int L, int R)
{
    int mid=(L+R)/2;
    treemax[2*node]+=lazy[node];
    treemax[2*node+1]+=lazy[node];
    treemin[2*node]+=lazy[node];
    treemin[2*node+1]+=lazy[node];
    lazy[2*node]+=lazy[node];
    lazy[2*node+1]+=lazy[node];
    lazy[node]=0;
}
int firstx(int node, int L, int R, int x)///first at least x
{
    if(L==R)
    {
        return L;
    }
    push(node,L,R);
    int mid=(L+R)/2;
    if(treemax[2*node]>=x)return firstx(2*node,L,mid,x);
    else if(treemax[2*node+1]>=x)return firstx(2*node+1,mid+1,R,x);
    else return n;
}
int lastx(int node, int L, int R, int x)
{
    if(L==R)
    {
        return L;
    }
    push(node,L,R);
    int mid=(L+R)/2;
    if(treemin[2*node+1]<=x)return lastx(2*node+1,mid+1,R,x);
    else if(treemin[2*node]<=x)return lastx(2*node,L,mid,x);
    else return -1;
}
void update(int node, int L, int R, int _left, int _right, int val)
{
    if(L>=_left && R<=_right)
    {
        treemin[node]+=val;
        treemax[node]+=val;
        lazy[node]+=val;
        return;
    }
    if(L>_right || R<_left)return;
    push(node,L,R);
    int mid=(L+R)/2;
    update(2*node,L,mid,_left,_right,val);
    update(2*node+1,mid+1,R,_left,_right,val);
    treemin[node]=min(treemin[2*node],treemin[2*node+1]);
    treemax[node]=max(treemax[2*node],treemax[2*node+1]);
}
int get(int node, int L, int R, int x)
{
    if(L==R)
    {
        return treemin[node];
    }
    push(node,L,R);
    int mid=(L+R)/2;
    if(x>mid)return get(2*node+1,mid+1,R,x);
    else return get(2*node,L,mid,x);
}
int main()
{
    cin>>n>>q;
    for(int i=0; i<n; i++)
    {
        cin>>niza[i];
    }
    sort(niza,niza+n);
    for(int i=0; i<n; i++)cout<<niza[i]<<" ";
    cout<<endl;
    build(1,0,n-1);
    for(int i=0; i<q; i++)
    {
        char type;
        cin>>type;
        if(type=='F')
        {
            int c,h;
            cin>>c>>h;
            int lborder=firstx(1,0,n-1,h);
            if(lborder==n)continue;
            int rborder=min(n-1,lborder+c-1);
            //cout<<"l r: "<<lborder+1<<" "<<rborder+1<<endl;
            int elborder=get(1,0,n-1,rborder);
            int lastofthat=lastx(1,0,n-1,elborder);
            //cout<<"last of number: "<<elborder<<" is: "<<lastofthat+1<<endl;
            if(rborder==lastofthat)
            {
                //cout<<"get full range: "<<endl;
                update(1,0,n-1,lborder,rborder,1);
                continue;
            }
            elborder--;
            int prevlast=lastx(1,0,n-1,elborder);
            //cout<<"last of number: "<<elborder<<" is: "<<prevlast+1<<endl;
            update(1,0,n-1,lborder,prevlast,1);
            //cout<<"so updating from: "<<lborder+1<<" to: "<<prevlast+1<<endl;
            int leftt=c-(prevlast-lborder+1);
            int newl=lastofthat-leftt+1;
            //cout<<"and from: "<<newl+1<<" "<<lastofthat+1<<endl;
            update(1,0,n-1,newl,lastofthat,1);
        }
        else
        {
            int mnn,mxx;
            cin>>mnn>>mxx;
            int x=firstx(1,0,n-1,mnn);
            int y=lastx(1,0,n-1,mxx);
            if(x==n)
            {
                cout<<0<<endl;
                continue;
            }
            cout<<y-x+1<<endl;
        }
    }
    return 0;
}
/*
5
2 3 5 6 6
*/

Compilation message

grow.cpp: In function 'void push(int, int, int)':
grow.cpp:25:9: warning: unused variable 'mid' [-Wunused-variable]
   25 |     int mid=(L+R)/2;
      |         ^~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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