oj.uz

Submission #890250

# Submission time Handle Problem Language Result Execution time Memory
890250 2023-12-20T19:42:47 Z idiotcomputer Growing Trees (BOI11_grow) C++11
100 / 100
 502 ms 4192 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e5+1;

int segtree[4*mxN+1];

void upd(int l, int r, int idx, int tl, int tr){
    if (tr < tl){
        return;
    }
    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 tl;
    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);
            if (l + c - 1 >= n){
                upd(0,n-1,0,l,n-1);
                continue;
            }
            tl = glowest(vals,query(0,n-1,0,l+c-1)+vals[l+c-1]);
            r = ghigh(vals,tl);
            upd(0,n-1,0,l,tl-1);
            c -= (tl-l);
            upd(0,n-1,0,r-c+1,r);
            /*
            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+1);
           /* 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;
           /* if ((r == n) || (vals[r] + query(0,n-1,0,r) > h)){
                res -= 1;
            }*/
            cout << res << '\n';
        }
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 2396 KB Output is correct
2 Correct 379 ms 4000 KB Output is correct
3 Correct 230 ms 3924 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 5 ms 1884 KB Output is correct
3 Correct 7 ms 1884 KB Output is correct
4 Correct 4 ms 2136 KB Output is correct
5 Correct 145 ms 2936 KB Output is correct
6 Correct 194 ms 3316 KB Output is correct
7 Correct 12 ms 1880 KB Output is correct
8 Correct 103 ms 2808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 2324 KB Output is correct
2 Correct 186 ms 3444 KB Output is correct
3 Correct 3 ms 1880 KB Output is correct
4 Correct 119 ms 2952 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 2412 KB Output is correct
2 Correct 197 ms 3152 KB Output is correct
3 Correct 23 ms 2140 KB Output is correct
4 Correct 176 ms 3396 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 2576 KB Output is correct
2 Correct 358 ms 3664 KB Output is correct
3 Correct 49 ms 2396 KB Output is correct
4 Correct 188 ms 3556 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 2388 KB Output is correct
2 Correct 373 ms 3680 KB Output is correct
3 Correct 234 ms 3924 KB Output is correct
4 Correct 51 ms 2468 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 2908 KB Output is correct
2 Correct 247 ms 3704 KB Output is correct
3 Correct 260 ms 3864 KB Output is correct
4 Correct 53 ms 2660 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 2388 KB Output is correct
2 Correct 368 ms 3848 KB Output is correct
3 Correct 54 ms 2908 KB Output is correct
4 Correct 260 ms 3444 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 2704 KB Output is correct
2 Correct 370 ms 3980 KB Output is correct
3 Correct 502 ms 4192 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 2804 KB Output is correct