oj.uz

Submission #890242

# Submission time Handle Problem Language Result Execution time Memory
890242 2023-12-20T18:51:17 Z idiotcomputer Growing Trees (BOI11_grow) C++11
0 / 100
 1000 ms 3844 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 989 ms 3624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 3124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 3248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 848 ms 3376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 3244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1022 ms 2908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 873 ms 3844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 3408 KB Time limit exceeded
2 Halted 0 ms 0 KB -