oj.uz

Submission #993110

# Submission time Handle Problem Language Result Execution time Memory
993110 2024-06-05T10:16:33 Z wood Growing Trees (BOI11_grow) C++17
100 / 100
 318 ms 6512 KB 
#include <bits/stdc++.h>  
using namespace std;
 
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay

struct segtree
{
    int size = 1, lazy[(int)1e6] = {0};
    segtree(int n){while(size<n) size*=2;}

    void upd(int l, int r){
        upd(l,r,0,0,size);
    }
    void upd(int l, int r, int x, int lx, int rx){
        if(lx>=r||rx<=l) return;
        if(lx>=l&&rx<=r){
            lazy[x]++;
            return;
        }
        int m = (lx+rx)/2;
        upd(l,r,2*x+1,lx,m);
        upd(l,r,2*x+2,m,rx); 
    }
    int get(int i){
        return get(i,0,0,size);
    }
    int get(int i, int x, int l, int r){
        if(r-l==1) return lazy[x];
        int m = (r+l)/2;
        int res;
        if(i<m) res = get(i,2*x+1,l,m);
        else res = get(i,2*x+2,m,r);
        return res+lazy[x];
    }
};


int main()
{
    fast_cin();
    #ifndef ONLINE_JUDGE
        #ifdef _WIN32
            freopen("input.in", "r", stdin);
            freopen("input.out", "w", stdout);
        #endif
    #endif
    int n,m; cin>>n>>m;
    int arr [n];
    for(int & sub : arr){
        cin>>sub;
    }
    segtree sgt(n);
    sort(arr,arr+n);
    for (size_t i = 0; i < m; i++)
    {
        char t; cin>>t;
        if(t=='F'){
            int h,c; cin>>c>>h;
            //binary search the element with at least h
            int l = -1, r = n;
            while(r-l>1){
                int mid = (r+l)/2;
                if(sgt.get(mid)+arr[mid]<h) l = mid;
                else r = mid;
            }
            if(r+c-1>n-1) c = n-r;
            int last_tree = r+c-1;
            //binary search the index with value strictly less than the value of r
            int la = -1, ra = n;
            while(ra-la>1){
                int mid = (ra+la)/2;
                if(sgt.get(mid)+arr[mid]>=sgt.get(last_tree)+arr[last_tree]) ra = mid;
                else la = mid;
            }
            int done = la+1-r;
            if(la>=r) sgt.upd(r,la + 1);
            else done = 0;
            //binary search largest index with value not greater than r;
            la = 0, ra = n;
            while(ra-la>1){
                int mid = (ra+la)/2;
                if(sgt.get(mid)+arr[mid]>sgt.get(last_tree)+arr[last_tree]) ra = mid;
                else la = mid;
            }
            sgt.upd(la+1+done-c,la+1);
        }
        else{
            int mn, mx; cin>>mn>>mx;
            int l = -1, r = n;
            while(r-l>1){
                int mid = (r+l)/2;
                if(arr[mid]+sgt.get(mid)<mn) l = mid;
                else r = mid;
            }
            int p = r;
            l = -1, r = n;
            while(r-l>1){
                int mid = (r+l)/2;
                if(arr[mid]+sgt.get(mid)<=mx) l = mid;
                else r = mid;
            }
            cout<<r-p<<'\n';
        }
    }
    
    return 0;
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:73:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |     for (size_t i = 0; i < m; i++)
      |                        ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 4700 KB Output is correct
2 Correct 256 ms 6228 KB Output is correct
3 Correct 180 ms 6196 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4188 KB Output is correct
2 Correct 5 ms 4220 KB Output is correct
3 Correct 5 ms 4188 KB Output is correct
4 Correct 4 ms 4188 KB Output is correct
5 Correct 77 ms 4560 KB Output is correct
6 Correct 78 ms 4688 KB Output is correct
7 Correct 10 ms 4444 KB Output is correct
8 Correct 43 ms 5100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 4696 KB Output is correct
2 Correct 88 ms 5712 KB Output is correct
3 Correct 3 ms 4188 KB Output is correct
4 Correct 53 ms 5296 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 4764 KB Output is correct
2 Correct 88 ms 5716 KB Output is correct
3 Correct 18 ms 4440 KB Output is correct
4 Correct 87 ms 5780 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 4632 KB Output is correct
2 Correct 238 ms 5972 KB Output is correct
3 Correct 26 ms 4696 KB Output is correct
4 Correct 143 ms 5904 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 4692 KB Output is correct
2 Correct 240 ms 5972 KB Output is correct
3 Correct 183 ms 6484 KB Output is correct
4 Correct 26 ms 4700 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 4744 KB Output is correct
2 Correct 155 ms 5972 KB Output is correct
3 Correct 195 ms 6228 KB Output is correct
4 Correct 26 ms 4636 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 4712 KB Output is correct
2 Correct 241 ms 4688 KB Output is correct
3 Correct 43 ms 5460 KB Output is correct
4 Correct 131 ms 5712 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 4960 KB Output is correct
2 Correct 240 ms 6364 KB Output is correct
3 Correct 318 ms 6512 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 5200 KB Output is correct