oj.uz

Submission #842585

# Submission time Handle Problem Language Result Execution time Memory
842585 2023-09-03T04:52:03 Z tuannm Growing Trees (BOI11_grow) C++17
100 / 100
 116 ms 4024 KB 
#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 1e5 + 1;
const string NAME = "";
const int lim = 2147483647;
//const long long lim = 9223372036854775807;
const double pi = acos(-1);
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int n, m, a[N], tree[4 * N], bonus[4 * N];

void down(int s){
    int t = bonus[s];
    bonus[2 * s] += t;
    tree[2 * s] += t;
    bonus[2 * s + 1] += t;
    tree[2 * s + 1] += t;
    bonus[s] = 0;
}

void build(int s, int l, int r){
    if(l == r){
        tree[s] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * s, l, mid);
    build(2 * s + 1, mid + 1, r);
    tree[s] = max(tree[2 * s], tree[2 * s + 1]);
}

void update(int s, int l, int r, int u, int v, int val){
    if(v < l || u > r)
        return;
    if(u <= l && r <= v){
        tree[s] += val;
        bonus[s] += val;
        return;
    }
    int mid = (l + r) / 2;
    down(s);
    update(2 * s, l, mid, u, v, val);
    update(2 * s + 1, mid + 1, r, u, v, val);
    tree[s] = max(tree[2 * s], tree[2 * s + 1]);
}

int get_id(int s, int l, int r, int x){
    if(l == r){
        if(tree[s] >= x)
            return l;
        return n + 1;
    }
    int mid = (l + r) / 2;
    down(s);
    if(tree[2 * s] >= x)
        return get_id(2 * s, l, mid, x);
    return get_id(2 * s + 1, mid + 1, r, x);
}

int get(int s, int l, int r, int x){
    if(l == r)
        return tree[s];
    int mid = (l + r) / 2;
    down(s);
    if(x <= mid)
        return get(2 * s, l, mid, x);
    return get(2 * s + 1, mid + 1, r, x);
}

void inp(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
}

void solve(){
    sort(a + 1, a + n + 1);
    build(1, 1, n);
    while(m--){
        char c;
        int x, y;
        cin >> c >> x >> y;
        if(c == 'F'){
            int tmp1 = get_id(1, 1, n, y);
            if(tmp1 == n + 1)
                continue;
            int tmp2 = min(tmp1 + x - 1, n);
            int v = get(1, 1, n, tmp2);
            int p = get_id(1, 1, n, v);
            int q = get_id(1, 1, n, v + 1) - 1;
            update(1, 1, n, tmp1, p - 1, 1);
            update(1, 1, n, q - tmp2 + p, q, 1);
        }
        else{
            cout << get_id(1, 1, n, y + 1) - get_id(1, 1, n, x) << "\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef TimeCalculation
        auto starttime = chrono::high_resolution_clock::now();
    #endif

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

    inp();
    solve();

    #ifdef TimeCalculation
        auto endtime = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count();
        cout << "\n=====" << "\nTime elapsed: " << duration << " ms\n";
    #endif
}

/*
5 7
1 3 2 5 2
F 2 1
C 3 6
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5
*/

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3500 KB Output is correct
2 Correct 83 ms 3416 KB Output is correct
3 Correct 75 ms 3356 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 31 ms 2876 KB Output is correct
6 Correct 37 ms 2888 KB Output is correct
7 Correct 5 ms 2396 KB Output is correct
8 Correct 20 ms 2824 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2908 KB Output is correct
2 Correct 38 ms 2920 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 26 ms 2816 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2868 KB Output is correct
2 Correct 39 ms 2816 KB Output is correct
3 Correct 7 ms 2396 KB Output is correct
4 Correct 37 ms 2916 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2908 KB Output is correct
2 Correct 76 ms 3412 KB Output is correct
3 Correct 12 ms 2648 KB Output is correct
4 Correct 57 ms 3164 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 3408 KB Output is correct
2 Correct 75 ms 3520 KB Output is correct
3 Correct 70 ms 3164 KB Output is correct
4 Correct 12 ms 2648 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3428 KB Output is correct
2 Correct 54 ms 3376 KB Output is correct
3 Correct 76 ms 3164 KB Output is correct
4 Correct 11 ms 2652 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 3364 KB Output is correct
2 Correct 83 ms 3600 KB Output is correct
3 Correct 21 ms 3420 KB Output is correct
4 Correct 47 ms 3456 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 3464 KB Output is correct
2 Correct 76 ms 3444 KB Output is correct
3 Correct 116 ms 3428 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4024 KB Output is correct