oj.uz

Submission #1023595

# Submission time Handle Problem Language Result Execution time Memory
1023595 2024-07-15T03:26:25 Z AtinaR Growing Trees (BOI11_grow) C++14
100 / 100
 209 ms 5968 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 5204 KB Output is correct
2 Correct 145 ms 5392 KB Output is correct
3 Correct 70 ms 5344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 6 ms 560 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 114 ms 1684 KB Output is correct
6 Correct 147 ms 1872 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 105 ms 1404 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 1776 KB Output is correct
2 Correct 135 ms 1880 KB Output is correct
3 Correct 4 ms 608 KB Output is correct
4 Correct 137 ms 1564 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 2132 KB Output is correct
2 Correct 146 ms 1888 KB Output is correct
3 Correct 8 ms 604 KB Output is correct
4 Correct 144 ms 2132 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 3152 KB Output is correct
2 Correct 139 ms 4960 KB Output is correct
3 Correct 35 ms 1688 KB Output is correct
4 Correct 78 ms 5060 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 4832 KB Output is correct
2 Correct 147 ms 5200 KB Output is correct
3 Correct 69 ms 5204 KB Output is correct
4 Correct 35 ms 1624 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 4944 KB Output is correct
2 Correct 117 ms 5044 KB Output is correct
3 Correct 72 ms 5480 KB Output is correct
4 Correct 36 ms 1628 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 5712 KB Output is correct
2 Correct 147 ms 4948 KB Output is correct
3 Correct 37 ms 4432 KB Output is correct
4 Correct 108 ms 4868 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 5460 KB Output is correct
2 Correct 136 ms 5520 KB Output is correct
3 Correct 132 ms 5632 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 5968 KB Output is correct