Submission #987575

#	Time	Username	Problem	Language	Result	Execution time	Memory
987575		Neco_arc	Growing Trees (BOI11_grow)	C++17	100 / 100	77 ms	3412 KiB

grow

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define VietAnh "Growing Trees"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

int n, q;
int a[maxn], bit[maxn];

void update(int x, int val) {
    while(x < maxn) bit[x] += val, x += (x & -x);
}

void Range_update(int l, int r) {
    update(l, 1), update(r + 1, -1);
}

int get(int x) {
    int s = a[x];
    while(x > 0) s += bit[x], x -= (x & -x);
    return s;
}

int find_first(int x)
{
    int l = 1, r = n;

    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(get(mid) < x) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

int find_last(int x)
{
    int l = 1, r = n;

    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(get(mid) <= x) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}

void solve()
{

    cin >> n >> q;

    fi(i, 1, n) cin >> a[i];
    sort(a + 1, a + 1 + n);

    fi(_, 1, q)
    {
        char type;
        int C, H;

        cin >> type >> C >> H;

        if(type == 'F')
        {
            int l = find_first(H), r = min(n, l + C - 1);

            if(r < n && get(r) == get(r + 1)){
                int L = max(l, find_first(get(r)));
                int R = find_last(get(r));

                int sl = r - L + 1;
                Range_update(R - sl + 1, R);
                Range_update(l, L - 1);
            }
            else Range_update(l, r);
        }
        else cout << find_last(H) - find_first(C) + 1 << '\n';
    }

}


int main()
{

    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(VietAnh".inp", "r")) {
        freopen(VietAnh".inp", "r", stdin);
        freopen(VietAnh".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;

    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(VietAnh".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(VietAnh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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