oj.uz

Submission #378632

# Submission time Handle Problem Language Result Execution time Memory
378632 2021-03-17T02:34:33 Z ntabc05101 Growing Trees (BOI11_grow) C++14
100 / 100
 112 ms 3520 KB 
#ifndef LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>

const int max_n=100000;
const int log_n=17;

int n, m;
int a[max_n+5];
int bits[max_n+5];

void update(int x, int delta) {
        for (; x<=max_n; x+=x&-x) {
                bits[x]+=delta;
        }
}

int get(int x) {
        int ret=0;
        for (; x>0; x&=x-1) {
                ret+=bits[x];
        }

        return ret;
}

int lower_x(int x) {
        int idx=0;
        for (int k=(1<<log_n); k>0; k>>=1) {
                if (idx+k<=n and get(idx+k)<x) {
                        idx+=k;
                }
        }

        return ++idx;
}

int main() {
        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        std::cin>>n>>m;
        for (int i=1; i<=n; ++i) std::cin>>a[i];
        std::sort(a+1, a+n+1);
        for (int i=1; i<=n; ++i) {
                update(i, a[i]), update(i+1, -a[i]);
        }

        while (m--) {
                char type; std::cin>>type;

                if (type=='F') {
                        int c, h; std::cin>>c>>h;
                        int i=lower_x(h);
                        if (i+c>n) {
                                update(i, 1);
                        }
                        else {
                                int x=get(i+c-1);
                                int j=lower_x(x), k=lower_x(x+1)-1;
                                update(i, 1), update(j, -1);
                                update(k-c+j-i+1, 1), update(k+1, -1);
                        }
                }
                else {
                        int low, high; std::cin>>low>>high;
                        std::cout<<lower_x(high+1)-lower_x(low)<<"\n";
                }
        }

        return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 2412 KB Output is correct
2 Correct 96 ms 2792 KB Output is correct
3 Correct 45 ms 2668 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 55 ms 1516 KB Output is correct
6 Correct 65 ms 1772 KB Output is correct
7 Correct 5 ms 492 KB Output is correct
8 Correct 31 ms 1260 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1772 KB Output is correct
2 Correct 52 ms 1900 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 72 ms 1388 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2028 KB Output is correct
2 Correct 61 ms 1772 KB Output is correct
3 Correct 6 ms 492 KB Output is correct
4 Correct 56 ms 1824 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2080 KB Output is correct
2 Correct 86 ms 2408 KB Output is correct
3 Correct 19 ms 1004 KB Output is correct
4 Correct 41 ms 2284 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2156 KB Output is correct
2 Correct 91 ms 2444 KB Output is correct
3 Correct 48 ms 2592 KB Output is correct
4 Correct 18 ms 876 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 2156 KB Output is correct
2 Correct 69 ms 2592 KB Output is correct
3 Correct 47 ms 2724 KB Output is correct
4 Correct 16 ms 876 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 2796 KB Output is correct
2 Correct 86 ms 2324 KB Output is correct
3 Correct 29 ms 1900 KB Output is correct
4 Correct 64 ms 2300 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 2600 KB Output is correct
2 Correct 91 ms 2708 KB Output is correct
3 Correct 112 ms 3052 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3520 KB Output is correct