Submission #471720

#	Time	Username	Problem	Language	Result	Execution time	Memory
471720		Karliver	Growing Trees (BOI11_grow)	C++14	100 / 100	135 ms	3340 KiB

grow

    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 2e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}
int n, q, a[N], bit[N];

void add(int l, int r, int x) { // add x to [l, r] 
    if (r < l) return;
    for ( ; l < n; l |= l + 1) bit[l] += x;
    for ( ++r; r < n; r |= r + 1) bit[r] -= x;
}
int query(int i) { // point query at i
    int sum = 0;
    for ( ; i >= 0; i &= i + 1, --i) sum += bit[i];
    return sum;
}

template<class T, class U> T firstTrue(T lo, T hi, U f) {
    assert(lo <= hi); ++hi; // assuming f is increasing
    while (lo < hi) { // find first index such that f is true 
        T mid = lo + (hi - lo) / 2;
        f(mid) ? hi = mid : lo = mid + 1; 
    } 
    return lo;
}

void solve() {

    cin >> n >> q;

    forn(i, n) cin >> a[i];
    sort(a, a + n);
    forn(i, n) add(i, i, a[i]);

    forn(pt, q) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if(c == 'F') {
            int l = firstTrue(0, n -1, [&](int i) {
                return query(i) >= b;
            });
            
            
            if(l == n)
                continue;
            int r = l + a - 1;
            if(r >= n -1) {
                add(l, n - 1, 1);
                continue;
            }
            int x = query(r);

            int l_ = firstTrue(l, n -1, [&](int i) {
                return query(i) >= x;
            });
            
            int r_ = firstTrue(l_, n -1, [&](int i) {
                return query(i) > x;
            }) - 1;
            add(l, l_ -1, 1);
            add(r_ - (a - (l_ - l)) + 1, r_, 1);
        }
        else {
            int l = firstTrue(0, n -1, [&](int i) {
                return query(i) >= a;
            });

            int r = firstTrue(0, n -1, [&](int i) {
                return query(i) > b;
            });
            cout << r - l << '\n';
        }
    }




}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

• 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