oj.uz

Submission #987575

# Submission time Handle Problem Language Result Execution time Memory
987575 2024-05-23T05:29:26 Z Neco_arc Growing Trees (BOI11_grow) C++17
100 / 100
 77 ms 3412 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2388 KB Output is correct
2 Correct 71 ms 2860 KB Output is correct
3 Correct 30 ms 2760 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 1 ms 536 KB Output is correct
5 Correct 36 ms 1364 KB Output is correct
6 Correct 41 ms 1720 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 20 ms 1116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1628 KB Output is correct
2 Correct 42 ms 1872 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 25 ms 1352 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2016 KB Output is correct
2 Correct 46 ms 1800 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 43 ms 1876 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2136 KB Output is correct
2 Correct 74 ms 2384 KB Output is correct
3 Correct 13 ms 860 KB Output is correct
4 Correct 26 ms 2312 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2132 KB Output is correct
2 Correct 76 ms 2388 KB Output is correct
3 Correct 30 ms 2560 KB Output is correct
4 Correct 14 ms 860 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2132 KB Output is correct
2 Correct 46 ms 2384 KB Output is correct
3 Correct 30 ms 2644 KB Output is correct
4 Correct 13 ms 1004 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2896 KB Output is correct
2 Correct 75 ms 2404 KB Output is correct
3 Correct 19 ms 1884 KB Output is correct
4 Correct 44 ms 2132 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2640 KB Output is correct
2 Correct 71 ms 2840 KB Output is correct
3 Correct 59 ms 2896 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 3412 KB Output is correct