oj.uz

Submission #1011439

# Submission time Handle Problem Language Result Execution time Memory
1011439 2024-06-30T13:45:58 Z doducanh Growing Trees (BOI11_grow) C++14
100 / 100
 71 ms 3372 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int a[maxn];
int n,q;
struct BIT{
    int n;
    vector<int>t;
    BIT(){}
    BIT(int n):n(n),t(n+7,0){}
    void up(int x,int val){
        for(;x<=n;x+=(x&(-x)))t[x]+=val;
    }
    void add(int l,int r,int val){
        up(l,val);
        up(r+1,-val);
    }
    int get(int x){
        int ans=0;
        for(;x;x-=(x&(-x)))ans+=t[x];
        return ans;
    }
};
BIT t;
int Findthefirst(int val){
    int l=1,r=n;
    int res=n+1;
    while(l<=r){
        int m=(l+r)/2;
        if(t.get(m)>=val){
            res=m;
            r=m-1;
        }
        else l=m+1;
    }
    return res;
}
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);
    t=BIT(n);
    for(int i=1;i<=n;i++){
        t.add(i,i,a[i]);
    }
    while(q--){
        char c;
        int a,b;
        cin>>c>>a>>b;
        if(c=='F'){
            int l=Findthefirst(b);
            int r=l+a-1;
            if(r>n){
                t.add(l,n,1);
                continue;
            }
            int x=t.get(r);
            int l_=Findthefirst(x);
            int r_=Findthefirst(x+1)-1;
            t.add(l,l_-1,1);
            t.add(r_-(a-(l_-l))+1,r_,1);
        }
        else{
            int l=Findthefirst(a);
            int r=Findthefirst(b+1);
            cout<<r-l<<"\n";
        }
    }
}

Compilation message

grow.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2384 KB Output is correct
2 Correct 70 ms 2644 KB Output is correct
3 Correct 39 ms 2652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 28 ms 1352 KB Output is correct
6 Correct 30 ms 1656 KB Output is correct
7 Correct 3 ms 344 KB Output is correct
8 Correct 17 ms 1116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1880 KB Output is correct
2 Correct 34 ms 1792 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 20 ms 1372 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1876 KB Output is correct
2 Correct 41 ms 1812 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 34 ms 1804 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2132 KB Output is correct
2 Correct 60 ms 2388 KB Output is correct
3 Correct 12 ms 860 KB Output is correct
4 Correct 33 ms 2404 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2128 KB Output is correct
2 Correct 61 ms 2384 KB Output is correct
3 Correct 39 ms 2652 KB Output is correct
4 Correct 11 ms 860 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2312 KB Output is correct
2 Correct 39 ms 2296 KB Output is correct
3 Correct 43 ms 2640 KB Output is correct
4 Correct 11 ms 856 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 2712 KB Output is correct
2 Correct 60 ms 2384 KB Output is correct
3 Correct 20 ms 1880 KB Output is correct
4 Correct 37 ms 2128 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2880 KB Output is correct
2 Correct 68 ms 2640 KB Output is correct
3 Correct 70 ms 3024 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3372 KB Output is correct