oj.uz

Submission #624508

# Submission time Handle Problem Language Result Execution time Memory
624508 2022-08-08T11:04:34 Z kakayoshi Growing Trees (BOI11_grow) C++17
100 / 100
 135 ms 2952 KB 
#include <bits/stdc++.h>
using namespace std;
#define forw(i,a,b) for(int i=a;i<=b;i++)
#define forb(i,a,b) for(int i=a;i>=b;i--)
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define getbit(mask,i) ((mask>>i)&1)
typedef long long int ll;
const ll maxN=5e5+5;
const ll mod=1e9+7;
const ll oo=1e18;
struct fenwick
{
    int n;
    vector <int> fen;
    fenwick(int _n=1e5)
    {
        n=_n;
        fen.assign(n+5,0);
    }
    void update(int pos, int val)
    {
        for(;pos<=n;pos+=pos&-pos) fen[pos]+=val;
        return;
    }
    void update(int l, int r, int val)
    {
        update(l,val);
        update(r+1,-val);
        return;
    }
    int get(int pos)
    {
        int ans=0;
        for(;pos;pos-=pos&-pos) ans+=fen[pos];
        return ans;
    }
}fen;
int n,q,a[maxN];
int find_pos(int val)
{
    int l=1;
    int r=n;
    int ans=n+1;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (fen.get(mid)>=val)
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ans;
}
void solve()
{
    cin>>n>>q;
    forw(i,1,n)
        cin>>a[i];
    sort(a+1,a+1+n);
    forw(i,1,n)
        fen.update(i,i,a[i]);
    while (q--)
    {
        char c; cin>>c;
        if (c=='F')
        {
            int c,h; cin>>c>>h;
            int l=find_pos(h);
            if (l==n+1) continue;
            c=min(c,n-l+1);
            int r=l+c-1;
            if (r<n && fen.get(r)==fen.get(r+1))
            {
                h=fen.get(r);
                int pos=find_pos(h);
                int add=r-pos+1;
                r=pos-1;
                fen.update(l,r,1);
                pos=find_pos(h+1);
                fen.update(pos-add,pos-1,1);
            }
            else
                fen.update(l,r,1);
        }
        else
        {
            int l,r; cin>>l>>r;
            cout<<find_pos(r+1)-find_pos(l)<<"\n";
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2376 KB Output is correct
2 Correct 99 ms 2580 KB Output is correct
3 Correct 36 ms 2316 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 3 ms 776 KB Output is correct
3 Correct 3 ms 744 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 49 ms 1744 KB Output is correct
6 Correct 55 ms 2000 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 27 ms 1460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2032 KB Output is correct
2 Correct 53 ms 2132 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 34 ms 1660 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2212 KB Output is correct
2 Correct 63 ms 2064 KB Output is correct
3 Correct 5 ms 744 KB Output is correct
4 Correct 53 ms 2136 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2104 KB Output is correct
2 Correct 91 ms 2400 KB Output is correct
3 Correct 17 ms 1104 KB Output is correct
4 Correct 32 ms 2376 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2132 KB Output is correct
2 Correct 106 ms 2444 KB Output is correct
3 Correct 39 ms 2308 KB Output is correct
4 Correct 18 ms 1108 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2128 KB Output is correct
2 Correct 71 ms 2376 KB Output is correct
3 Correct 39 ms 2400 KB Output is correct
4 Correct 19 ms 1168 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 2512 KB Output is correct
2 Correct 135 ms 2252 KB Output is correct
3 Correct 26 ms 1736 KB Output is correct
4 Correct 65 ms 2152 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 2596 KB Output is correct
2 Correct 104 ms 2684 KB Output is correct
3 Correct 85 ms 2488 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 2952 KB Output is correct