oj.uz

Submission #873362

# Submission time Handle Problem Language Result Execution time Memory
873362 2023-11-14T23:24:47 Z bobbilyking Growing Trees (BOI11_grow) C++17
100 / 100
 341 ms 4568 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)

#define NN 100010

namespace seg {
    typedef ll T;
    T id=0;
    T f(T a, T b) {return a+b;}

    T t[2 * NN];
    ll n=NN;  // array size

    void _modify(ll p, T value) {  // set value at position p
      for (p+=n, t[p] += value; p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
    }

    T _query(ll l, ll r) { // fold f on interval [l, r)
      T resl=id, resr=id;
      for (l += n, r += n; l < r; l /= 2, r /= 2) {
        if (l&1) resl = f(resl, t[l++]);
        if (r&1) resr = f(t[--r], resr);
      }
      return f(resl, resr);
    }

    void modify(ll l, ll r, ll T) { // already inclusive exclusive we smart about it
        if (l>=r) return; // nothing should happen
        _modify(l, T);
        _modify(r, -T);
    }

    T query(ll i) {
        return _query(0, i+1);
    }
}

ll n;
pl get(ll lo, ll hi) {
    pl res;
    {
        ll l = -1, r = n;
        while (l+1<r){
            ll m =(l+r)/2;
            if (seg::query(m) < lo) l = m;
            else r = m;   
        }
        res.K = r;
    }
    {
        ll l = -1, r = n;
        while (l+1<r){
            ll m =(l+r)/2;
            if (seg::query(m) <= hi) l = m;
            else r = m;   
        }
        res.V = r;
    }
    return res;
}

int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    cin >> n; G(q)
    vector<ll> v;
    F(i, 0, n) {
        G(x) v.push_back(x);
    }
    sort(A(v));
    F(i, 0, n) {
        seg::modify(i, i+1, v[i]);
    }
    while (q--) {
        GS(s) if (s == "F") {
            G(c) G(h)
            assert(c>0);
            auto [st, _] = get(h, 2e9);
            if (st == n) continue;
            // cout << "YA " << st << endl;
            // cout << "?? " << n-1 << " " << st << " " << c-1 << endl;
            ll want = seg::query(min(n-1, st + c - 1));
            // cout << "HELLO? " << want << endl;
            auto [tl, tr] = get(want, want);
            // cout << "WTF " << tl << " " << tr << endl;
            seg::modify(st, tl, 1); c -= tl - st;
            seg::modify(max(tl, tr-c), tr, 1);

            // cout << "Added 1 to " << st << ", " << tl-1 << " and " << max(tl, tr-c) << ", " << tr << endl;
        } else {
            G(a) G(b)
            auto [l, r] = get(a, b);
            cout <<  r-l << '\n';
        }
        // F(i, 0, n) cout << seg::query(i) << " "; cout << endl;
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 2772 KB Output is correct
2 Correct 291 ms 4400 KB Output is correct
3 Correct 209 ms 4200 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 100 ms 720 KB Output is correct
6 Correct 113 ms 1016 KB Output is correct
7 Correct 9 ms 600 KB Output is correct
8 Correct 44 ms 1372 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 960 KB Output is correct
2 Correct 118 ms 1876 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 56 ms 1616 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 1044 KB Output is correct
2 Correct 133 ms 2132 KB Output is correct
3 Correct 15 ms 604 KB Output is correct
4 Correct 132 ms 1932 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 2196 KB Output is correct
2 Correct 284 ms 3732 KB Output is correct
3 Correct 35 ms 1448 KB Output is correct
4 Correct 170 ms 3560 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 2468 KB Output is correct
2 Correct 265 ms 3792 KB Output is correct
3 Correct 204 ms 3788 KB Output is correct
4 Correct 37 ms 1244 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 2516 KB Output is correct
2 Correct 152 ms 4040 KB Output is correct
3 Correct 209 ms 4156 KB Output is correct
4 Correct 34 ms 1244 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 2772 KB Output is correct
2 Correct 269 ms 2508 KB Output is correct
3 Correct 55 ms 3648 KB Output is correct
4 Correct 132 ms 3752 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 2920 KB Output is correct
2 Correct 275 ms 4348 KB Output is correct
3 Correct 341 ms 4568 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 3276 KB Output is correct