oj.uz

Submission #1034496

# Submission time Handle Problem Language Result Execution time Memory
1034496 2024-07-25T14:29:40 Z orcslop Growing Trees (BOI11_grow) C++17
100 / 100
 214 ms 7588 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); 
    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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 6352 KB Output is correct
2 Correct 154 ms 6900 KB Output is correct
3 Correct 54 ms 6676 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 4 ms 4452 KB Output is correct
3 Correct 4 ms 4440 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 54 ms 5560 KB Output is correct
6 Correct 67 ms 5716 KB Output is correct
7 Correct 6 ms 4444 KB Output is correct
8 Correct 33 ms 5216 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5712 KB Output is correct
2 Correct 71 ms 5772 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 42 ms 5336 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5792 KB Output is correct
2 Correct 73 ms 5696 KB Output is correct
3 Correct 11 ms 4632 KB Output is correct
4 Correct 69 ms 5700 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 6064 KB Output is correct
2 Correct 144 ms 6352 KB Output is correct
3 Correct 20 ms 4964 KB Output is correct
4 Correct 50 ms 6244 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 6220 KB Output is correct
2 Correct 157 ms 6356 KB Output is correct
3 Correct 61 ms 6708 KB Output is correct
4 Correct 22 ms 5044 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 6304 KB Output is correct
2 Correct 105 ms 6472 KB Output is correct
3 Correct 56 ms 6604 KB Output is correct
4 Correct 22 ms 5008 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 6844 KB Output is correct
2 Correct 164 ms 6392 KB Output is correct
3 Correct 50 ms 6108 KB Output is correct
4 Correct 143 ms 6228 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 6496 KB Output is correct
2 Correct 214 ms 6732 KB Output is correct
3 Correct 185 ms 7080 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 7588 KB Output is correct