oj.uz

Submission #689864

# Submission time Handle Problem Language Result Execution time Memory
689864 2023-01-29T15:05:53 Z hafo Growing Trees (BOI11_grow) C++14
100 / 100
 720 ms 4508 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 7;
const ll oo = 1e15 + 69;

int n, a[maxn], u, v, q;
char t;

struct ST {
    int st[4 * maxn], lz[4 * maxn];
    void build(int id, int l, int r) {
        if(l == r) {
            st[id] = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }

    void fix(int id, int l, int r) {
        if(!lz[id]) return;
        if(l == r) st[id] += lz[id];
        else {
            lz[id << 1] += lz[id];
            lz[id << 1 | 1] += lz[id];
        }
        lz[id] = 0;
    }

    void update(int id, int l, int r, int u, int v) {
        fix(id, l, r);
        if(r < u || l > v) return;
        if(u <= l && r <= v) {
            lz[id]++;
            fix(id, l, r);
            return;
        }
        int mid = l + r >> 1;
        update(id << 1, l, mid, u, v);
        update(id << 1 | 1, mid + 1, r, u, v);
    }

    int get(int id, int l, int r, int pos) {
        fix(id, l, r);
        if(r < pos || l > pos) return -1;
        if(l == r) return st[id];
        int mid = l + r >> 1;
        return max(get(id << 1, l, mid, pos), get(id << 1 | 1, mid + 1, r, pos));
    }

    int get(int pos) {
        return get(1, 1, n, pos);
    }
} st;

int bs(int x) {
    int l = 1, r = n, res = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(st.get(mid) >= x) {
            r = mid - 1;
            res = mid;
        } else l = mid + 1;
    }
    return res;
}

int bs2(int x) {
    int l = 1, r = n, res = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(st.get(mid) <= x) {
            l = mid + 1;
            res = mid;
        } else r = mid - 1;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>q;
    for(int i = 1; i <= n; i++) cin>>a[i];
    sort(a + 1, a + 1 + n);
    st.build(1, 1, n);

    while(q--) {
        cin>>t>>u>>v;
        if(t == 'F') {
            int le = bs(v);
            if(le == -1) continue;
            int ri = min(n, le + u - 1), l = bs(st.get(ri)), r = bs2(st.get(ri));
            if(le <= l - 1) st.update(1, 1, n, le, l - 1);
            if(max(l, r - u + (l - le) + 1) <= r) st.update(1, 1, n, max(l, r - u + (l - le) + 1), r);
//            for(int i = 1; i <= n; i++) cout<<st.get(i)<<" ";
//            cout<<"\n";
        } else {
            int low = bs(u), high = bs2(v);
            cout<<(low == -1 || high == -1 ? 0:high - low + 1)<<"\n";
        }
    }
    return 0;
}

Compilation message

grow.cpp: In member function 'void ST::build(int, int, int)':
grow.cpp:31:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In member function 'void ST::update(int, int, int, int, int)':
grow.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In member function 'int ST::get(int, int, int, int)':
grow.cpp:63:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In function 'int bs(int)':
grow.cpp:75:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In function 'int bs2(int)':
grow.cpp:87:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 2620 KB Output is correct
2 Correct 546 ms 4112 KB Output is correct
3 Correct 489 ms 4144 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 5 ms 400 KB Output is correct
5 Correct 194 ms 1480 KB Output is correct
6 Correct 243 ms 1680 KB Output is correct
7 Correct 17 ms 472 KB Output is correct
8 Correct 139 ms 1240 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 808 KB Output is correct
2 Correct 250 ms 2004 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 175 ms 1452 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 844 KB Output is correct
2 Correct 281 ms 1788 KB Output is correct
3 Correct 34 ms 468 KB Output is correct
4 Correct 245 ms 1940 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 1644 KB Output is correct
2 Correct 539 ms 3724 KB Output is correct
3 Correct 62 ms 1228 KB Output is correct
4 Correct 403 ms 3784 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 2512 KB Output is correct
2 Correct 522 ms 3984 KB Output is correct
3 Correct 491 ms 4056 KB Output is correct
4 Correct 61 ms 1200 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 2640 KB Output is correct
2 Correct 373 ms 3920 KB Output is correct
3 Correct 483 ms 4044 KB Output is correct
4 Correct 63 ms 1208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 2488 KB Output is correct
2 Correct 516 ms 3816 KB Output is correct
3 Correct 80 ms 3216 KB Output is correct
4 Correct 346 ms 3768 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 2724 KB Output is correct
2 Correct 499 ms 4172 KB Output is correct
3 Correct 720 ms 4508 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 3008 KB Output is correct