oj.uz

Submission #1034485

# Submission time Handle Problem Language Result Execution time Memory
1034485 2024-07-25T14:19:58 Z orcslop Growing Trees (BOI11_grow) C++17
10 / 100
 170 ms 5924 KB 
#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); 
    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 = 1, 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; 
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 5592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4188 KB Output is correct
2 Incorrect 3 ms 4428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 4880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 5072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 5336 KB Output is correct
2 Incorrect 163 ms 5336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 5336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 5336 KB Output is correct
2 Incorrect 148 ms 5340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 5340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 5924 KB Output is correct