oj.uz

Submission #837148

# Submission time Handle Problem Language Result Execution time Memory
837148 2023-08-25T03:09:30 Z fanwen Growing Trees (BOI11_grow) C++17
100 / 100
 130 ms 6088 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4692 KB Output is correct
2 Correct 95 ms 5012 KB Output is correct
3 Correct 98 ms 4812 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 31 ms 1512 KB Output is correct
6 Correct 37 ms 1764 KB Output is correct
7 Correct 5 ms 568 KB Output is correct
8 Correct 17 ms 1236 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1868 KB Output is correct
2 Correct 36 ms 1868 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 26 ms 1508 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2012 KB Output is correct
2 Correct 38 ms 1828 KB Output is correct
3 Correct 9 ms 688 KB Output is correct
4 Correct 44 ms 1904 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3788 KB Output is correct
2 Correct 88 ms 4380 KB Output is correct
3 Correct 14 ms 1336 KB Output is correct
4 Correct 86 ms 4228 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 4092 KB Output is correct
2 Correct 90 ms 4516 KB Output is correct
3 Correct 96 ms 4440 KB Output is correct
4 Correct 12 ms 1364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 4292 KB Output is correct
2 Correct 65 ms 4692 KB Output is correct
3 Correct 95 ms 4828 KB Output is correct
4 Correct 12 ms 1308 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 5112 KB Output is correct
2 Correct 95 ms 4352 KB Output is correct
3 Correct 37 ms 4564 KB Output is correct
4 Correct 56 ms 4652 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 4804 KB Output is correct
2 Correct 87 ms 5084 KB Output is correct
3 Correct 130 ms 5588 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 6088 KB Output is correct