Submission #378632

#	Time	Username	Problem	Language	Result	Execution time	Memory
378632		ntabc05101	Growing Trees (BOI11_grow)	C++14	100 / 100	112 ms	3520 KiB

grow

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10