oj.uz

Submission #441305

# Submission time Handle Problem Language Result Execution time Memory
441305 2021-07-04T22:03:36 Z SirCovidThe19th Growing Trees (BOI11_grow) C++14
100 / 100
 328 ms 3348 KB 
#include <bits/stdc++.h>
using namespace std;

const int mx = 1e5+5;

int n, q, tmp[mx], bit[mx];

void upd(int l, int r, int val){
    for (; l <= n; l += l&(-l)) bit[l] += val;
    for (++r; r <= n; r += r&(-r)) bit[r] -= val;
}
int query(int i){
    int ret = 0;
    for (; i > 0; i -= i&(-i)) ret += bit[i];
    return ret;
}
int search(int val){ //index of first element greater/equal to val
    int low = 1, high = n+1;
    while (low < high){
        int mid = (low+high)/2;
        if (query(mid) >= val) high = mid;
        else low = mid+1;
    }return low;    
}

int main(){ 
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> tmp[i];
    sort(tmp+1, tmp+n+1);
    for (int i = 1; i <= n; i++) upd(i, i, tmp[i]);
    while (q--){
        char t; int a, b; cin >> t >> a >> b; 
        if (t == 'F'){ 
            int l = search(b), r = l+a-1; 
            if (l > n) continue;
            else if (r >= n) upd(l, n, 1);
            else{
                int fr = search(query(r)), lr = search(query(r)+1)-1;
                upd(l, fr-1, 1); upd(lr-(r-fr), lr, 1);
            }  
        }else{
            int l = search(a), r = search(b+1)-1;
            cout<<r-l+1<<endl;
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 2244 KB Output is correct
2 Correct 239 ms 2656 KB Output is correct
3 Correct 108 ms 2628 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 9 ms 364 KB Output is correct
3 Correct 10 ms 376 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 220 ms 1344 KB Output is correct
6 Correct 258 ms 1604 KB Output is correct
7 Correct 11 ms 332 KB Output is correct
8 Correct 212 ms 1088 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 1576 KB Output is correct
2 Correct 232 ms 1872 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 200 ms 1280 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 1876 KB Output is correct
2 Correct 254 ms 1576 KB Output is correct
3 Correct 12 ms 460 KB Output is correct
4 Correct 236 ms 1772 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 1956 KB Output is correct
2 Correct 242 ms 2168 KB Output is correct
3 Correct 59 ms 808 KB Output is correct
4 Correct 91 ms 2372 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 1936 KB Output is correct
2 Correct 271 ms 2280 KB Output is correct
3 Correct 102 ms 2460 KB Output is correct
4 Correct 73 ms 776 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 2068 KB Output is correct
2 Correct 190 ms 2240 KB Output is correct
3 Correct 121 ms 2516 KB Output is correct
4 Correct 60 ms 804 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 2628 KB Output is correct
2 Correct 261 ms 2244 KB Output is correct
3 Correct 64 ms 1728 KB Output is correct
4 Correct 187 ms 2148 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 2416 KB Output is correct
2 Correct 251 ms 2768 KB Output is correct
3 Correct 193 ms 2844 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 3348 KB Output is correct