Submission #890242

#	Time	Username	Problem	Language	Result	Execution time	Memory
890242		idiotcomputer	Growing Trees (BOI11_grow)	C++11	0 / 100	1044 ms	3844 KiB

grow

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

const int mxN = 1e5;

int segtree[4*mxN+1];

void upd(int l, int r, int idx, int tl, int tr){
    if (tl > r || tr < l){
        return;
    }
    if (l >= tl && r <= tr){
        segtree[idx] += 1;
        return;
    }
    int m = (l+r)/2;
    upd(l,m,2*idx+1,tl,tr);
    upd(m+1,r,2*idx+2,tl,tr);
}

int query(int l, int r, int idx, int t){
    if (t > r || l > t){
        return 0;
    }
    int res = segtree[idx];
    if (l == r){
        return res;
    }
    int m = (l+r)/2;
    return res + query(l,m,2*idx+1,t) + query(m+1,r,2*idx+2,t);
}

int glowest(vector<int> &vals, int t){
    int n = vals.size();
    int l = -1;
    int r = n;
    int curr;
    while (r - l > 1){
        curr = (l+r)/2;
        if (query(0,n-1,0,curr) + vals[curr] >= t){
            r = curr;   
        } else {
            l = curr;
        }
    }
    return r;
}

int ghigh(vector<int> &vals, int tl){
    int n = vals.size();
    int l = tl;
    int r = n;
    int tar = query(0,n-1,0,l) + vals[l];
    int curr;
    while (r - l > 1){
        curr = (l+r)/2;
        if (query(0,n-1,0,curr) + vals[curr] > tar){
            r = curr;
        } else {
            l = curr;
        }
    }
    return l;
}

int main()
{
    memset(segtree,0,sizeof(segtree));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n,m;
    cin >> n >> m;
    
    vector<int> vals(n);
    for (int i =0; i < n; i++){
        cin >> vals[i];
    }
    sort(vals.begin(),vals.end());
    
    char w;
    int c,h;
    int l,r;
    int res;
   /* for (int i =0; i < 3*1e8; i++){
        continue;
    }
    for (int i =0; i < n; i++){
        cout << vals[i] << " ";
    }
    cout << '\n';*/
    for (int i =0; i < m; i++){
        cin >> w;
      //  cout << w << ": ";
        if (w == 'F'){
            cin >> c >> h;
         //   cout << h << "\n";
            l = glowest(vals,h);
            while (l < n){
                r = ghigh(vals,l);
              //  cout << c << ", " << l << "," << r << '\n';
                if (r - l+1 >= c){
                    upd(0,n-1,0,r-c+1,r);
                    break;
                } 
                upd(0,n-1,0,l,r);
                c -= (r-l+1);
                l = r+1;
            }
           // r = ghigh(vals,l);
           // cout << l << "," << r << '\n';
           /* if (r - l+1 >= c){
                upd(0,n-1,0,r-c+1,r);
            } else {
                upd(0,n-1,0,l,l+c-1);
            }*/
        } else {
            cin >> c >> h;
           // cout << c << " , " << h << "  ";
            l = glowest(vals,c);
            r = glowest(vals,h);
           /* cout << l << "," << r << '\n';
            for (int j = 0; j < n; j++){
                cout << vals[j] + query(0,n-1,0,j) << " ";
            }
            cout << '\n';*/
            res = r -l+1;
            if ((r == n) || (vals[r] + query(0,n-1,0,r) > h)){
                res -= 1;
            }
            cout << res << '\n';
        }
    }
    return 0;
}

• 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