oj.uz

Submission #846582

# Submission time Handle Problem Language Result Execution time Memory
846582 2023-09-08T02:53:50 Z LTTrungCHL Growing Trees (BOI11_grow) C++17
100 / 100
 147 ms 6420 KB 
///***LTT***///
/// ->TUYEN QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define CHECKBIT(mask,i) ((mask>>(i) )&1) // == 1 la bat, == 0 la tat
#define OFFBIT(mask,i) ((1<<(i))^mask) // tat bit thu i
#define ONBIT(mask,i) ((1<<(i))mask) // bat bit thu i
using namespace std;
const long long oo = 1e9+7;
const int N = 1e5 + 10;
pair <int, int> tree[N * 4];
int lazy[N * 4];
int a[N], n, q;
char type;
void build(int id,int l,int r){
    if (l == r){
        tree[id].F = a[l];
        tree[id].S = a[l];
        return;
    }
    int mid = (l + r)/2;
    build(id*2,l,mid);
    build(id*2 + 1,mid + 1,r);
    tree[id].F = max(tree[id * 2].F, tree[id * 2 + 1].F);
    tree[id].S = min(tree[id * 2].S, tree[id * 2 + 1].S);
    return;
}
void down(int id,int l,int r){
    if (l != r){
        tree[id*2].F += lazy[id];
        tree[id*2 + 1].F += lazy[id];
        tree[id*2 + 1].S += lazy[id];
        tree[id*2 ].S += lazy[id];
        lazy[id*2] += lazy[id];
        lazy[id*2 + 1] += lazy[id];
    }
    lazy[id] = 0;
}
int cnpl(int id,int l,int r,int k){
    if (lazy[id]){
        down(id,l,r);
    }
    if (l == r){
        if (tree[id].F < k) return n + 1;
        return r;
    }
    int mid = (l + r)/2;
    if (tree[id * 2].F >= k) return cnpl(id * 2,l,mid,k);
    return cnpl(id * 2 + 1,mid + 1,r,k);
}
int cnpr(int id,int l,int r,int k){
    if (lazy[id]){
        down(id,l,r);
    }
    if (l == r){
        if (tree[id].S > k) return 0;
        return r;
    }
    int mid = (l + r)/2;
    if (tree[id * 2 + 1].S <= k) return cnpr(id * 2 + 1,mid + 1,r,k);
    return cnpr(id * 2 ,l,mid ,k);
}
void update(int id,int l,int r,int u,int v){
    if (lazy[id]){
        down(id,l,r);
    }
    if (l > v or r < u) return;
    if (l >= u and r <= v){
        tree[id].F++;
        tree[id].S++;
        lazy[id]++;
        return;
    }
    int mid = (l + r)/2;
    update(id * 2,l,mid,u,v);
    update(id * 2 + 1,mid + 1,r,u,v);
    tree[id].F = max(tree[id * 2].F, tree[id * 2 + 1].F);
    tree[id].S = min(tree[id * 2].S, tree[id * 2 + 1].S);
    return;
}
int get(int id,int l,int r,int u){
    if (lazy[id]){
        down(id,l,r);
    }
    if (l > u or r < u) return 0;
    if (l == u and r == u){
        return tree[id].F;
    }
    int mid = (l + r)/2;
    return max(get(id*2,l,mid,u), get(id*2+1,mid+1,r,u));

}
void inp(){
    cin >> n >> q;
    for (int i = 1;i <= n;i++){
        cin >> a[i];
    }
    return;
}
void solve(){
    sort(a + 1, a + n + 1);
    build(1,1,n);
    for (int i = 1;i <= q;i++){
        cin >> type;
        if (type == 'F'){
                int h, c;
            cin >> c >> h;
            int l = cnpl(1,1,n,h);
            int nxt = 0;
            if (l + c - 1< n){
                int val = get(1,1,n,l + c - 1);
                nxt = cnpl(1,1,n,val);
                if (nxt - 1 >= l)
                update(1,1,n,l, nxt - 1);
                int sl = (l + c - 1) - nxt + 1;
                if (get(1,1,n,l + c) == val){
                    int r = cnpr(1,1,n,val);
                    update(1,1,n,r - sl + 1, r);
                } else update(1,1,n,nxt,nxt + ((l + c - 1) - nxt));
            } else update(1,1,n,l, min(n, l + c - 1));
        } else {
            int l, r;
            cin >> l >> r;
            r = cnpr(1,1,n,r);
            l = cnpl(1,1,n,l);
            cout << r - l + 1 <<"\n";
        }
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen("file.inp", "r")){
        freopen("file.inp", "r", stdin);
        freopen("file.out", "w", stdout);
    }
    //int t;
    //cin >> t;
    //while(t--){
    inp();
    solve();
    //}
}
/*
5 8
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
C 0 0
*/

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4948 KB Output is correct
2 Correct 93 ms 6360 KB Output is correct
3 Correct 32 ms 6420 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 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2524 KB Output is correct
5 Correct 31 ms 3420 KB Output is correct
6 Correct 36 ms 3640 KB Output is correct
7 Correct 4 ms 2396 KB Output is correct
8 Correct 17 ms 3164 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2852 KB Output is correct
2 Correct 37 ms 3928 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 20 ms 3480 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2908 KB Output is correct
2 Correct 39 ms 3676 KB Output is correct
3 Correct 10 ms 2652 KB Output is correct
4 Correct 43 ms 3848 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4952 KB Output is correct
2 Correct 89 ms 5968 KB Output is correct
3 Correct 15 ms 5036 KB Output is correct
4 Correct 27 ms 5868 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 4748 KB Output is correct
2 Correct 84 ms 4696 KB Output is correct
3 Correct 31 ms 6232 KB Output is correct
4 Correct 14 ms 4956 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4888 KB Output is correct
2 Correct 63 ms 5972 KB Output is correct
3 Correct 32 ms 6232 KB Output is correct
4 Correct 10 ms 4956 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 4700 KB Output is correct
2 Correct 102 ms 4696 KB Output is correct
3 Correct 23 ms 5444 KB Output is correct
4 Correct 50 ms 5892 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 4948 KB Output is correct
2 Correct 84 ms 6224 KB Output is correct
3 Correct 147 ms 6360 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 5012 KB Output is correct