oj.uz

Submission #1038919

# Submission time Handle Problem Language Result Execution time Memory
1038919 2024-07-30T09:15:18 Z BF001 Growing Trees (BOI11_grow) C++17
100 / 100
 76 ms 4176 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define N 100005
#define int long long

int n, m, bit[N], a[N];

void ud(int l, int r, int val){
    if (l > r) return;
    while (l <= n){
        bit[l] += val;
        l += (l & (-l));
    }
    r++;
    while (r <= n){
        bit[r] -= val;
        r += (r & (-r));
    }
}

int get(int pos){
    int rt = 0;
    while (pos >= 1){
        rt += bit[pos];
        pos -= (pos & (-pos));
    }
    return rt;
}
 
int bin(int val){
    int rt = n + 1;
    int l = 1, r = n;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (get(mid) >= val){
            rt = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return rt;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++){
        ud(i, i, a[i]);
    }

    while (m--){
        char typ;
        cin >> typ;
        if (typ == 'F'){
            int c, h;
            cin >> c >> h;
            int l = bin(h);
            if (l == n + 1) continue;
            int r = l + c - 1;
            if (r >= n){
                ud(l, n, 1);
                continue;
            }
            int l2 = bin(get(r)) - 1;
            int r2 = bin(get(r) + 1) - 1;
            ud(l, l2, 1);
            l2 = r2 - (c - (l2 - l + 1)) + 1;
            ud(l2, r2, 1);
            continue;
        }
        int l, r;
        cin >> l >> r;
        l = bin(l);
        r = bin(r + 1) - 1;
        cout << r - l + 1 << "\n";
    }
 
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3144 KB Output is correct
2 Correct 76 ms 3412 KB Output is correct
3 Correct 34 ms 3380 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 1 ms 480 KB Output is correct
5 Correct 28 ms 1440 KB Output is correct
6 Correct 31 ms 1708 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 16 ms 1116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1620 KB Output is correct
2 Correct 34 ms 1876 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 19 ms 1376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2076 KB Output is correct
2 Correct 34 ms 1884 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 36 ms 1784 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2392 KB Output is correct
2 Correct 67 ms 2912 KB Output is correct
3 Correct 11 ms 1116 KB Output is correct
4 Correct 25 ms 3152 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2640 KB Output is correct
2 Correct 67 ms 2948 KB Output is correct
3 Correct 26 ms 3164 KB Output is correct
4 Correct 11 ms 1116 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2900 KB Output is correct
2 Correct 42 ms 3164 KB Output is correct
3 Correct 27 ms 3420 KB Output is correct
4 Correct 11 ms 1116 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3476 KB Output is correct
2 Correct 69 ms 2900 KB Output is correct
3 Correct 20 ms 2648 KB Output is correct
4 Correct 36 ms 2904 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3180 KB Output is correct
2 Correct 76 ms 3408 KB Output is correct
3 Correct 70 ms 3664 KB Output is correct

Subtask #10
10.0 / 10.0

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