oj.uz

Submission #842789

# Submission time Handle Problem Language Result Execution time Memory
842789 2023-09-03T11:31:11 Z vjudge1 Growing Trees (BOI11_grow) C++17
10 / 100
 660 ms 7800 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];
    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;
            });
            if(h>=get(1,1,n,r,r)) cout<<r-l+1<<'\n';
            else cout<<r-l<<'\n';
        }
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2396 KB Output is correct
2 Incorrect 9 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 7800 KB Output is correct