oj.uz

Submission #842887

# Submission time Handle Problem Language Result Execution time Memory
842887 2023-09-03T12:58:12 Z vjudge1 Growing Trees (BOI11_grow) C++17
90 / 100
 1000 ms 8060 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 525 ms 7688 KB Output is correct
2 Correct 703 ms 7668 KB Output is correct
3 Correct 545 ms 7260 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 11 ms 2580 KB Output is correct
3 Correct 10 ms 2588 KB Output is correct
4 Correct 6 ms 2392 KB Output is correct
5 Correct 269 ms 4744 KB Output is correct
6 Correct 383 ms 5056 KB Output is correct
7 Correct 22 ms 4740 KB Output is correct
8 Correct 243 ms 4948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 5032 KB Output is correct
2 Correct 364 ms 4960 KB Output is correct
3 Correct 6 ms 4700 KB Output is correct
4 Correct 278 ms 5216 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 4984 KB Output is correct
2 Correct 409 ms 5248 KB Output is correct
3 Correct 44 ms 4700 KB Output is correct
4 Correct 374 ms 5068 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 5504 KB Output is correct
2 Correct 710 ms 7528 KB Output is correct
3 Correct 93 ms 4848 KB Output is correct
4 Correct 413 ms 7260 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 7308 KB Output is correct
2 Correct 722 ms 7712 KB Output is correct
3 Correct 602 ms 7260 KB Output is correct
4 Correct 86 ms 4700 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 7656 KB Output is correct
2 Correct 653 ms 7488 KB Output is correct
3 Correct 593 ms 7324 KB Output is correct
4 Correct 94 ms 4820 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 7372 KB Output is correct
2 Correct 857 ms 7372 KB Output is correct
3 Correct 116 ms 7508 KB Output is correct
4 Correct 701 ms 7676 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 7676 KB Output is correct
2 Correct 875 ms 7676 KB Output is correct
3 Execution timed out 1028 ms 7256 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 8060 KB Output is correct