oj.uz

Submission #838839

# Submission time Handle Problem Language Result Execution time Memory
838839 2023-08-27T21:57:14 Z VMaksimoski008 Growing Trees (BOI11_grow) C++14
100 / 100
 662 ms 9520 KB 
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

struct SegTree {
    int n;
    vector<int> v;
    vector<ll> tree;
    vector<ll> lazy;

    SegTree(vector<int> const &_v) {
        this->v = _v;
        n = sz(v);
        tree.resize(4*n+5, 0);
        lazy.resize(4*n+5, 0);
    }

    void push(int u, int tl, int tr) {
        if(lazy[u] == 0) return ;

        tree[u] += (tr - tl + 1) * lazy[u];

        if(tl != tr) {
            lazy[2*u] += lazy[u];
            lazy[2*u+1] += lazy[u];
        }

        lazy[u] = 0;
    }

    void build(int u, int tl, int tr) {
        if(tl == tr) {
            tree[u] = v[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(2*u, tl, tm);
            build(2*u+1, tm+1, tr);
            tree[u] = tree[2*u] + tree[2*u+1];
        }
    }

    void update(int u, int tl, int tr, int l, int r, int val) {
        push(u, tl, tr);
        if(tl > tr || l > tr || tl > r) return ;

        if(l <= tl && tr <= r) {
            lazy[u] += val;
            push(u, tl, tr);
            return ;
        }

        int tm = (tl + tr) / 2;
        update(2*u, tl, tm, l, r, val);
        update(2*u+1, tm+1, tr, l, r, val);
        tree[u] = tree[2*u] + tree[2*u+1];
    }

    ll query(int u, int tl, int tr, int pos) {
        if(tl > tr || tl > pos || pos > tr) return 0;
        push(u, tl, tr);
        if(tl == tr) return tree[u];
        int tm = (tl + tr) / 2;
        if(pos <= tm)
            return query(2*u, tl, tm, pos);
        return query(2*u+1, tm+1, tr, pos);
    }

    void update(int l, int r, int val) {
        update(1, 0, n-1, l, r, val);
    }

    ll query(int pos) {
        return query(1, 0, n-1, pos);
    }
};

int32_t main() {
    setIO();

    int n, q;
    cin >> n >> q;

    vector<int> v(n);
    for(int &x : v) cin >> x;

    sort(all(v));

    SegTree tree(v);
    tree.build(1, 0, n-1);

    auto binSearch = [&](int l, int r, function<bool(int)> f) {
        int ans = n;

        while(l <= r) {
            int mid = (l + r) / 2;
            
            if(f(mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        return ans;
    };

    while(q--) {
        char t;
        cin >> t;

        if(t == 'F') {
            int c, h;
            cin >> c >> h;

            int q_l = binSearch(0, n-1, [&](int x) {
                return tree.query(x) >= h;
            });

            int q_r = q_l + c - 1;

            if(q_r >= n-1) {
                tree.update(q_l, q_r, 1);
                continue;
            }

            int newL = binSearch(q_l, n-1, [&](int x) {
                return tree.query(x) >= tree.query(q_r);
            });

            int newR = binSearch(newL, n-1, [&](int x) {
                return tree.query(x) > tree.query(q_r);
            }) - 1;

            tree.update(q_l, newL-1, 1);
            tree.update(newR - c + newL - q_l + 1, newR, 1);

            // for(int i=0; i<n; i++)
            //     cout << tree.query(i) << " ";
            // cout << '\n';
        } else {
            int a, b;
            cin >> a >> b;

            if(tree.query(n-1) < a) {
                cout << 0 << '\n';
                continue;
            }

            int l = binSearch(0, n-1, [&](int x) {
                return tree.query(x) >= a;
            });

            int r = binSearch(0, n-1, [&](int x) {
                return tree.query(x) > b;
            });

            cout << r - l << '\n';
        }
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 7804 KB Output is correct
2 Correct 432 ms 8088 KB Output is correct
3 Correct 132 ms 7752 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 128 ms 1740 KB Output is correct
6 Correct 160 ms 1892 KB Output is correct
7 Correct 13 ms 724 KB Output is correct
8 Correct 61 ms 1344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 2084 KB Output is correct
2 Correct 163 ms 2124 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 79 ms 1712 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 2252 KB Output is correct
2 Correct 183 ms 2088 KB Output is correct
3 Correct 30 ms 852 KB Output is correct
4 Correct 158 ms 2152 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 6076 KB Output is correct
2 Correct 402 ms 6816 KB Output is correct
3 Correct 41 ms 1876 KB Output is correct
4 Correct 104 ms 6724 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 6708 KB Output is correct
2 Correct 395 ms 7240 KB Output is correct
3 Correct 130 ms 6792 KB Output is correct
4 Correct 40 ms 1952 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 7060 KB Output is correct
2 Correct 273 ms 7824 KB Output is correct
3 Correct 132 ms 7608 KB Output is correct
4 Correct 40 ms 1876 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 8080 KB Output is correct
2 Correct 417 ms 7080 KB Output is correct
3 Correct 64 ms 8084 KB Output is correct
4 Correct 237 ms 7852 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 7884 KB Output is correct
2 Correct 413 ms 8152 KB Output is correct
3 Correct 662 ms 9168 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 9520 KB Output is correct