Submission #837148

#	Time	Username	Problem	Language	Result	Execution time	Memory
837148		fanwen	Growing Trees (BOI11_grow)	C++17	100 / 100	130 ms	6088 KiB

grow

#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

template <class T, T e, T g>
struct lazy_segment_tree {
    vector <T> it, lazy;
    int n;

    void modify(int idx, int l, int r, T val) {
        // do somethings
        it[idx] += val;
        lazy[idx] += val;
    }

    T merge(const T &a, const T &b) {
        // do somethings;
        return max(a, b);
    }

    void push(int idx, int l, int r) {
        if(lazy[idx] == g) return;
        int mid = l + r >> 1;
        modify(idx << 1, l, mid, lazy[idx]);
        modify(idx << 1 | 1, mid + 1, r, lazy[idx]);
        lazy[idx] = g;
    }

    void update(int idx, int l, int r, int u, int v, T val) {
        if(l > v || r < u || u > v) return;
        if(l >= u && r <= v) {
            modify(idx, l, r, val);
            return;
        }
        push(idx, l, r);
        int mid = l + r >> 1;
        update(idx << 1, l, mid, u, v, val);
        update(idx << 1 | 1, mid + 1, r, u, v, val);
        it[idx] = merge(it[idx << 1], it[idx << 1 | 1]);
    }

    T get(int idx, int l, int r, int u, int v) {
        if(l > v || r < u) return e;
        if(l >= u && r <= v) return it[idx];
        push(idx, l, r);
        int mid = l + r >> 1;
        return merge(get(idx << 1, l, mid, u, v), get(idx << 1 | 1, mid + 1, r, u, v));
    }

    int find(int idx, int l, int r, int val) {
        if(it[idx] < val) return n + 1;
        if(l == r) return l;
        push(idx, l, r);
        int mid = l + r >> 1;
        return (it[idx << 1] >= val ? find(idx << 1, l, mid, val) : find(idx << 1 | 1, mid + 1, r, val));
    }
public :

    explicit lazy_segment_tree(int n) :
        n(n), lazy(n << 2 | 1, g), it(n << 2 | 1) {}

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

    T get(int l, int r) {
        return get(1, 1, n, l, r);
    }

    T get(int u) {
        return get(u, u);
    }

    int find(T val) {
        return find(1, 1, n, val);
    }
};

const int MAXN = 1e5 + 5;

int N, M, a[MAXN];

void you_make_it(void) {
    cin >> N >> M;
    FOR(i, 1, N) cin >> a[i];
    lazy_segment_tree <int, 0, 0> it(N);
    sort(a + 1, a + N + 1);
    FOR(i, 1, N) it.update(i, i, a[i]);
    FOR(i, 1, M) {
        char op; int a, b; cin >> op >> a >> b;
        if(op == 'F') {
            int l = it.find(b);
            if(l > N) continue;
            int r = l + a - 1;
            if(r > N) {
                it.update(l, N, 1);
                continue;
            }
            int x = it.get(r);
            int ll = it.find(x), rr = it.find(x + 1) - 1;
            it.update(l, ll - 1, 1);
            it.update(rr - (a - (ll - l)) + 1, rr, 1);
        } else {
            cout << (it.find(b + 1)) - it.find(a) << '\n';
        }
    }
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message (stderr)

grow.cpp: In instantiation of 'lazy_segment_tree<T, e, g>::lazy_segment_tree(int) [with T = int; T e = 0; T g = 0]':
grow.cpp:99:39:   required from here
grow.cpp:21:9: warning: 'lazy_segment_tree<int, 0, 0>::n' will be initialized after [-Wreorder]
   21 |     int n;
      |         ^
grow.cpp:20:20: warning:   'std::vector<int> lazy_segment_tree<int, 0, 0>::lazy' [-Wreorder]
   20 |     vector <T> it, lazy;
      |                    ^~~~
grow.cpp:72:14: warning:   when initialized here [-Wreorder]
   72 |     explicit lazy_segment_tree(int n) :
      |              ^~~~~~~~~~~~~~~~~
grow.cpp:20:20: warning: 'lazy_segment_tree<int, 0, 0>::lazy' will be initialized after [-Wreorder]
   20 |     vector <T> it, lazy;
      |                    ^~~~
grow.cpp:20:16: warning:   'std::vector<int> lazy_segment_tree<int, 0, 0>::it' [-Wreorder]
   20 |     vector <T> it, lazy;
      |                ^~
grow.cpp:72:14: warning:   when initialized here [-Wreorder]
   72 |     explicit lazy_segment_tree(int n) :
      |              ^~~~~~~~~~~~~~~~~
grow.cpp: In instantiation of 'void lazy_segment_tree<T, e, g>::update(int, int, int, int, int, T) [with T = int; T e = 0; T g = 0]':
grow.cpp:76:15:   required from 'void lazy_segment_tree<T, e, g>::update(int, int, T) [with T = int; T e = 0; T g = 0]'
grow.cpp:101:38:   required from here
grow.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In instantiation of 'int lazy_segment_tree<T, e, g>::find(int, int, int, int) [with T = int; T e = 0; T g = 0]':
grow.cpp:88:20:   required from 'int lazy_segment_tree<T, e, g>::find(T) [with T = int; T e = 0; T g = 0]'
grow.cpp:105:30:   required from here
grow.cpp:67:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In instantiation of 'void lazy_segment_tree<T, e, g>::push(int, int, int) [with T = int; T e = 0; T g = 0]':
grow.cpp:48:9:   required from 'void lazy_segment_tree<T, e, g>::update(int, int, int, int, int, T) [with T = int; T e = 0; T g = 0]'
grow.cpp:76:15:   required from 'void lazy_segment_tree<T, e, g>::update(int, int, T) [with T = int; T e = 0; T g = 0]'
grow.cpp:101:38:   required from here
grow.cpp:36:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In instantiation of 'T lazy_segment_tree<T, e, g>::get(int, int, int, int, int) [with T = int; T e = 0; T g = 0]':
grow.cpp:80:19:   required from 'T lazy_segment_tree<T, e, g>::get(int, int) [with T = int; T e = 0; T g = 0]'
grow.cpp:84:19:   required from 'T lazy_segment_tree<T, e, g>::get(int) [with T = int; T e = 0; T g = 0]'
grow.cpp:112:29:   required from here
grow.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid = l + r >> 1;
      |                   ~~^~~

• 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