oj.uz

Submission #442477

# Submission time Handle Problem Language Result Execution time Memory
442477 2021-07-07T20:57:41 Z JovanB Growing Trees (BOI11_grow) C++17
100 / 100
 248 ms 6080 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int MAXN = 100000;

struct Segment{
    int mn, mx, lazy;
} seg[4*MAXN+5];

int a[MAXN+5];

void init(int node, int l, int r){
    if(l == r){
        seg[node].mn = seg[node].mx = a[l];
        return;
    }
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
    seg[node].mn = seg[node*2].mn;
    seg[node].mx = seg[node*2+1].mx;
}

void propagate(int node, int l, int r){
    seg[node].mn += seg[node].lazy;
    seg[node].mx += seg[node].lazy;
    if(l == r){
        seg[node].lazy = 0;
        return;
    }
    seg[node*2].lazy += seg[node].lazy;
    seg[node*2+1].lazy += seg[node].lazy;
    seg[node].lazy = 0;
}

void upd(int node, int l, int r, int tl, int tr){
    propagate(node, l, r);
    if(tl > r || l > tr || tl > tr) return;
    if(tl <= l && r <= tr){
        seg[node].lazy++;
        propagate(node, l, r);
        return;
    }
    int mid = (l+r)/2;
    upd(node*2, l, mid, tl, tr);
    upd(node*2+1, mid+1, r, tl, tr);
    seg[node].mn = seg[node*2].mn;
    seg[node].mx = seg[node*2+1].mx;
}

int qpoint(int node, int l, int r, int x){
    propagate(node, l, r);
    if(l == r) return seg[node].mn;
    int mid = (l+r)/2;
    if(x <= mid) return qpoint(node*2, l, mid, x);
    return qpoint(node*2+1, mid+1, r, x);
}

int qmin(int node, int l, int r, int val){
    propagate(node, l, r);
    if(l == r){
        if(seg[node].mn >= val) return l;
        return l+1;
    }
    int mid = (l+r)/2;
    propagate(node*2, l, mid);
    propagate(node*2+1, mid+1, r);
    if(seg[node*2].mx >= val) return qmin(node*2, l, mid, val);
    return qmin(node*2+1, mid+1, r, val);
}

int qmax(int node, int l, int r, int val){
    propagate(node, l, r);
    if(l == r){
        if(seg[node].mn <= val) return l;
        return l-1;
    }
    int mid = (l+r)/2;
    propagate(node*2, l, mid);
    propagate(node*2+1, mid+1, r);
    if(seg[node*2+1].mn <= val) return qmax(node*2+1, mid+1, r, val);
    return qmax(node*2, l, mid, val);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+1+n);
    init(1, 1, n);
    while(m--){
        char typ;
        cin >> typ;
        if(typ == 'F'){
            int c, h;
            cin >> c >> h;
            int l = qmin(1, 1, n, h);
            if(l > n) continue;
            int r = l + c - 1;
            if(r > n) r = n;
            int vl = qpoint(1, 1, n, r);
            int dr = qmax(1, 1, n, vl);
            int dl = 1 + qmax(1, 1, n, vl-1);
            int sc = r - dl + 1;
            upd(1, 1, n, l, dl-1);
            upd(1, 1, n, dr-sc+1, dr);
        }
        else{
            int mn, mx;
            cin >> mn >> mx;
            cout << max(0, qmax(1, 1, n, mx) - qmax(1, 1, n, mn-1)) << "\n";
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 5140 KB Output is correct
2 Correct 180 ms 5624 KB Output is correct
3 Correct 206 ms 5352 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 57 ms 1512 KB Output is correct
6 Correct 77 ms 1716 KB Output is correct
7 Correct 7 ms 616 KB Output is correct
8 Correct 56 ms 1220 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 1736 KB Output is correct
2 Correct 79 ms 1836 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 62 ms 1468 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2016 KB Output is correct
2 Correct 80 ms 1760 KB Output is correct
3 Correct 14 ms 588 KB Output is correct
4 Correct 70 ms 1904 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 3272 KB Output is correct
2 Correct 151 ms 5132 KB Output is correct
3 Correct 19 ms 1484 KB Output is correct
4 Correct 155 ms 5016 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 4724 KB Output is correct
2 Correct 154 ms 5132 KB Output is correct
3 Correct 193 ms 5308 KB Output is correct
4 Correct 18 ms 1484 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 4868 KB Output is correct
2 Correct 116 ms 5116 KB Output is correct
3 Correct 195 ms 5348 KB Output is correct
4 Correct 18 ms 1500 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 5376 KB Output is correct
2 Correct 149 ms 4956 KB Output is correct
3 Correct 39 ms 4428 KB Output is correct
4 Correct 123 ms 4880 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 5244 KB Output is correct
2 Correct 152 ms 5404 KB Output is correct
3 Correct 248 ms 5572 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 6080 KB Output is correct