oj.uz

답안 #842894

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
842894 2023-09-03T13:00:51 Z Eliorita Growing Trees (BOI11_grow) C++14
0 / 100
 414 ms 3212 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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 100010
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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 260 ms 2904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 7 ms 348 KB Output is correct
3 Incorrect 2 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 282 ms 3212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 368 ms 2904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 290 ms 3044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 414 ms 3072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 313 ms 3108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 3152 KB Output isn't correct
2 Halted 0 ms 0 KB -