oj.uz

Submission #842897

# Submission time Handle Problem Language Result Execution time Memory
842897 2023-09-03T13:05:50 Z vjudge1 Growing Trees (BOI11_grow) C++17
100 / 100
 877 ms 7912 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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 459 ms 7764 KB Output is correct
2 Correct 668 ms 7396 KB Output is correct
3 Correct 435 ms 7260 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Output is correct
2 Correct 8 ms 2652 KB Output is correct
3 Correct 10 ms 2392 KB Output is correct
4 Correct 5 ms 2396 KB Output is correct
5 Correct 246 ms 4756 KB Output is correct
6 Correct 321 ms 5156 KB Output is correct
7 Correct 23 ms 4696 KB Output is correct
8 Correct 206 ms 4952 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 5004 KB Output is correct
2 Correct 319 ms 5200 KB Output is correct
3 Correct 5 ms 4700 KB Output is correct
4 Correct 228 ms 4784 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 5396 KB Output is correct
2 Correct 352 ms 4944 KB Output is correct
3 Correct 37 ms 4700 KB Output is correct
4 Correct 314 ms 5096 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 5244 KB Output is correct
2 Correct 604 ms 7536 KB Output is correct
3 Correct 83 ms 4848 KB Output is correct
4 Correct 363 ms 7256 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 7284 KB Output is correct
2 Correct 599 ms 7328 KB Output is correct
3 Correct 463 ms 7260 KB Output is correct
4 Correct 89 ms 4864 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 7756 KB Output is correct
2 Correct 448 ms 7572 KB Output is correct
3 Correct 461 ms 7508 KB Output is correct
4 Correct 91 ms 4696 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 7912 KB Output is correct
2 Correct 640 ms 7464 KB Output is correct
3 Correct 92 ms 7496 KB Output is correct
4 Correct 491 ms 7504 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 7668 KB Output is correct
2 Correct 655 ms 7644 KB Output is correct
3 Correct 877 ms 7472 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 7908 KB Output is correct