oj.uz

Submission #842886

# Submission time Handle Problem Language Result Execution time Memory
842886 2023-09-03T12:57:25 Z Eliorita Growing Trees (BOI11_grow) C++14
100 / 100
 981 ms 8272 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define x first
#define y second
#define getbit(u,i) ((u>>i)&1)
#define all(x) x.begin(),x.end()
#define N 200001
using namespace std;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
int n,q,a[N];
struct node
{
    int val,lazy;
} tree[400010];
void build(int id,int l,int r)
{
    if(l==r)
    {
        tree[id].val=a[l];
        return;
    }
    int m=(l+r)/2;
    build(id*2,l,m);
    build(id*2+1,m+1,r);
    tree[id].val=tree[id*2].val+tree[id*2+1].val;
}
void down(int id,int l,int r)
{
    tree[id].val+=tree[id].lazy*(r-l+1);
    if(l!=r)
    {
        tree[id*2].lazy+=tree[id].lazy;
        tree[id*2+1].lazy+=tree[id].lazy;
    }
    tree[id].lazy=0;
}
void update(int id,int l,int r,int u,int v,int val)
{
    down(id,l,r);
    if(l>v||r<u) return;
    else if(l>=u&&r<=v)
    {
        tree[id].val+=val*(r-l+1);
        if(l!=r)
        {
            tree[id*2].lazy+=val;
            tree[id*2+1].lazy+=val;
        }
        return;
    }
    int m=(l+r)/2;
    update(id*2,l,m,u,v,val);
    update(id*2+1,m+1,r,u,v,val);
    tree[id].val=tree[id*2].val+tree[id*2+1].val;
}
int get(int id,int l,int r,int u,int v)
{
    down(id,l,r);
    if(l>v||r<u) return 0;
    else if(l>=u&&r<=v) return tree[id].val;
    int m=(l+r)/2;
    return get(id*2,l,m,u,v)+get(id*2+1,m+1,r,u,v);
}
int binary(int l,int r,function<bool(int)> f)
{
    int ans=n;
    while(l<=r)
    {
        int m=(l+r)/2;
        if(f(m))
        {
            ans=m;
            r=m-1;
        }
        else l=m+1;
    }
    return ans;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    n++;
    a[n]=INT_MAX;
    sort(a+1,a+n+1);
    build(1,1,n);
    while(q--)
    {
        char t;
        int c,h;
        cin>>t>>c>>h;
        if(t=='F')
        {
            int l=binary(1,n,[&](int x)
            {
                return get(1,1,n,x,x)>=h;
            });
            int r=l+c-1;
            if(r>=n)
            {
                update(1,1,n,l,n,1);
                continue;
            }
            int val=get(1,1,n,r,r);
            int lhs=binary(l,n,[&](int x)
            {
                return get(1,1,n,x,x)>=val;
            });
            int rhs=binary(lhs,n,[&](int x)
            {
                return get(1,1,n,x,x)>val;
            })-1;
            update(1,1,n,l,lhs-1,1);
            update(1,1,n,rhs-c+lhs-l+1,rhs,1);
        }
        else
        {
            if(get(1,1,n,n,n)<c)
            {
                cout<<0<<'\n';
                continue;
            }
            int l=binary(1,n,[&](int x)
            {
                return get(1,1,n,x,x)>=c;
            });
            int r=binary(1,n,[&](int x)
            {
                return get(1,1,n,x,x)>h;
            });
            cout<<r-l<<'\n';
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 7760 KB Output is correct
2 Correct 742 ms 7500 KB Output is correct
3 Correct 485 ms 7256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2396 KB Output is correct
2 Correct 12 ms 2392 KB Output is correct
3 Correct 12 ms 2392 KB Output is correct
4 Correct 6 ms 2392 KB Output is correct
5 Correct 287 ms 4944 KB Output is correct
6 Correct 358 ms 5024 KB Output is correct
7 Correct 26 ms 4700 KB Output is correct
8 Correct 205 ms 4780 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 4944 KB Output is correct
2 Correct 356 ms 4952 KB Output is correct
3 Correct 5 ms 4696 KB Output is correct
4 Correct 284 ms 5032 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 5308 KB Output is correct
2 Correct 406 ms 4948 KB Output is correct
3 Correct 42 ms 4696 KB Output is correct
4 Correct 354 ms 4944 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 5268 KB Output is correct
2 Correct 667 ms 7256 KB Output is correct
3 Correct 92 ms 4848 KB Output is correct
4 Correct 433 ms 7256 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 7568 KB Output is correct
2 Correct 700 ms 7712 KB Output is correct
3 Correct 533 ms 7496 KB Output is correct
4 Correct 88 ms 4828 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 7360 KB Output is correct
2 Correct 518 ms 7772 KB Output is correct
3 Correct 545 ms 7324 KB Output is correct
4 Correct 88 ms 4824 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 7720 KB Output is correct
2 Correct 763 ms 7512 KB Output is correct
3 Correct 86 ms 7512 KB Output is correct
4 Correct 629 ms 7428 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 7644 KB Output is correct
2 Correct 683 ms 7400 KB Output is correct
3 Correct 981 ms 7476 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 8272 KB Output is correct