oj.uz

Submission #471720

# Submission time Handle Problem Language Result Execution time Memory
471720 2021-09-10T14:04:06 Z Karliver Growing Trees (BOI11_grow) C++14
100 / 100
 135 ms 3340 KB 
    
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2372 KB Output is correct
2 Correct 134 ms 2808 KB Output is correct
3 Correct 54 ms 2592 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 336 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 59 ms 1396 KB Output is correct
6 Correct 69 ms 1572 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 43 ms 1060 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 1656 KB Output is correct
2 Correct 69 ms 1792 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 42 ms 1288 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1888 KB Output is correct
2 Correct 79 ms 1836 KB Output is correct
3 Correct 8 ms 460 KB Output is correct
4 Correct 72 ms 1672 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 1972 KB Output is correct
2 Correct 115 ms 2272 KB Output is correct
3 Correct 21 ms 848 KB Output is correct
4 Correct 44 ms 2260 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 2020 KB Output is correct
2 Correct 116 ms 2468 KB Output is correct
3 Correct 46 ms 2500 KB Output is correct
4 Correct 21 ms 836 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 2236 KB Output is correct
2 Correct 83 ms 2312 KB Output is correct
3 Correct 62 ms 2580 KB Output is correct
4 Correct 20 ms 844 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 2684 KB Output is correct
2 Correct 121 ms 2260 KB Output is correct
3 Correct 33 ms 1740 KB Output is correct
4 Correct 73 ms 2176 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 2488 KB Output is correct
2 Correct 130 ms 2564 KB Output is correct
3 Correct 135 ms 2872 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 3340 KB Output is correct