Submission #1124256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124256		njoop	Growing Trees (BOI11_grow)	C++17	0 / 100	928 ms	6016 KiB

grow

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n, m, arr[100010], in, h, mn, mx, c;

struct lzt {
    vector<int> seg, lazy;

    void init() {
        seg.assign(600010, 0);
        lazy.assign(600010, 0);
    }

    void push(int l, int r, int node) {
        if(lazy[node] != 0) {
            seg[node] += (r-l+1)*lazy[node];
            if(l != r) {
                lazy[node*2] += lazy[node];
                lazy[node*2+1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    void update(int l, int r, int idl, int idr, int val, int node) {
        push(l, r, node);
        if(l > idr || r < idl) return;
        if(l >= idl && r <= idr) {
            seg[node] += (r-l+1)*val;
            if(l != r) {
                lazy[node*2] += val;
                lazy[node*2+1] += val;
            }
            return;
        }
        int mid = l + (r-l)/2;
        update(l, mid, idl, idr, val, node*2);
        update(mid+1, r, idl, idr, val, node*2+1);
        seg[node] = seg[node*2] + seg[node*2+1];
    }

    int query(int l, int r, int ql, int qr, int node) {
        push(l, r, node);
        if(l > qr || r < ql) return 0;
        if(l >= ql && r <= qr) return seg[node];
        int mid = l+(r-l)/2;
        return query(l, mid, ql, qr, node*2) + query(mid+1, r, ql, qr, node*2+1);
    }

    void upd(int l, int r, int val) {
        update(1, n, l, r, val, 1);
    }
    
    int qry(int l, int r) {
        return query(1, n, l, r, 1);
    }

    bool is_found(int val) {
        int l=1, r=n;
        while(l < r) {
            int mid = (l+r)/2;
            if(qry(mid, mid) >= val) {
                r = mid;
            } else {
                l = mid+1;
            }
        }
        if(l >= 1 && l <= n && qry(l, l) == val) return true;
        return false;
    }

    int lb_idx(int val) {
        int l=0, r=n+1;
        while(l < r) {
            int mid = (l+r)/2;
            if(qry(mid, mid) >= val) {
                r = mid;
            } else {
                l = mid+1;
            }
        }
        return l;
    }

    int ub_idx(int val) {
        int l=0, r=n+1;
        while(l < r) {
            int mid = (l+r)/2;
            if(qry(mid, mid) > val) {
                r = mid;
            } else {
                l = mid+1;
            }
        }
        return l;
    }
};

signed main() {
    lzt seg;
    char co;
    cin >> n >> m;
    seg.init();
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
    }
    sort(arr+1, arr+n+1);
    seg.upd(0, 0, -1);
    for(int i=1; i<=n; i++) {
        seg.upd(i, i, arr[i]);
    }
    seg.upd(n+1, n+1, 1e10);
    while(m--) {
        cin >> co;
        if(co == 'C') {
            cin >> mn >> mx;
            if(seg.ub_idx(mx)-seg.lb_idx(mn) <= 0) cout << 0 << "\n";
            else cout << seg.ub_idx(mx)-seg.lb_idx(mn) << "\n";
        } else {
            cin >> c >> h;
            int lb = seg.lb_idx(h);
            int rbv = seg.qry(lb+c-1, lb+c-1);
            int rb = seg.ub_idx(rbv)-1;
            int mb = seg.lb_idx(rbv);
            int ov = lb+c-1 - mb;
            if(mb-lb >= 1) {
                seg.upd(lb, mb-1, 1);
            } 
            seg.upd(rb-ov, rb, 1);
        }
    }
    return 0;
}

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:113:23: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+10' to '2147483647' [-Woverflow]
  113 |     seg.upd(n+1, n+1, 1e10);
      |                       ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10