Submission #1034496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034496		orcslop	Growing Trees (BOI11_grow)	C++17	100 / 100	214 ms	7588 KiB

grow

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define aint(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
#define mkp make_pair
#define pii pair<int, int>

template <class T> class BIT {
  private:
    int n;
    vector<T> bit;
    vector<T> arr;

  public:
    BIT(int n) : n(n), bit(n + 1), arr(n) {}

    void set(int k, T val) { add(k, val - arr[k]); }

    void add(int k, T val) {
        arr[k] += val;
        k++;
        for (; k <= n; k += k & -k) { bit[k] += val; }
    }

    T query(int a, int b) {
        b++;
        T s = 0;
        for (; a > 0; a -= a & -a) { s -= bit[a]; }
        for (; b > 0; b -= b & -b) { s += bit[b]; }
        return s;
    }
};


template <class T> class RURQBIT {
    private : 
        int n; 
        vector<T> a; 
        BIT<T> b, c; 
    public : 
        RURQBIT(int n) : n(n), a(n + 1), b(n + 2), c(n + 2){}

        void build(vector<T> &v){
            for(int i = 1; i <= sz(v); i++){
                a[i] = v[i - 1]; 
                b.set(i, a[i] - a[i - 1]); 
                c.set(i, i * (a[i] - a[i - 1])); 
            }
        }

        void add(int l, int r, T v){
            b.add(l, v); 
            b.add(r + 1, -v); 
            c.add(l, l * v); 
            c.add(r + 1, -(r + 1) * v); 
        }

        T query(int l, int r){
            T rs = (r + 1) * b.query(1, r) - c.query(1, r); 
            T ls = l * b.query(1, l - 1) - c.query(1, l - 1); 
            return rs - ls; 
        }
}; 

const int MAXN = 1e5 + 5; 

int n, q; 
vector<int> v; 
RURQBIT<int> bit(MAXN); 

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q; 
    for(int i = 0; i < n; i++){
        int x; 
        cin >> x; 
        v.pb(x); 
    }
    sort(v.begin(), v.end()); 
    bit.build(v); 
    int it = 0; 
    for(int i = 0; i < q; i++){
        char t; 
        cin >> t; 
        if(t == 'F'){
            int c, h; 
            cin >> c >> h; 
            int low = 1, high = n + 1; 
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (bit.query(mid, mid) >= h) high = mid;
                else low = mid + 1;
            }
            if(low == n + 1) {
                continue; 
            }; 
            int index = low; 
            if(index + c > n) {
                bit.add(index, n, 1); 
                continue; 
            }
            int val = bit.query(index + c - 1, index + c - 1); 
            low = index, high = n; 
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (bit.query(mid, mid) >= val) high = mid;
                else low = mid + 1;
            }
            int lb = low; 
            low = index, high = n; 
            while (low < high) {
                int mid = low + (high - low + 1) / 2;
                if (bit.query(mid, mid) <= val) low = mid; 
                else high = mid - 1;
            }
            int ub = low; 
            bit.add(index, lb - 1, 1); 
            bit.add(ub + lb - index - c + 1, ub, 1); 
        }
        else{
            int mn, mx; 
            cin >> mn >> mx; 
            int low = 1, high = n + 1; 
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (bit.query(mid, mid) >= mn) high = mid;
                else low = mid + 1;
            }
            int lb = low; 
            low = 0, high = n; 
            while (low < high) {
                int mid = low + (high - low + 1) / 2;
                if (bit.query(mid, mid) <= mx) low = mid; 
                else high = mid - 1;
            }
            int ub = low; 
            cout << ub - lb + 1 << '\n'; 
        }
    }
    return 0; 
}

Compilation message (stderr)

grow.cpp: In function 'int32_t main()':
grow.cpp:85:9: warning: unused variable 'it' [-Wunused-variable]
   85 |     int it = 0;
      |         ^~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10