oj.uz

Submission #846580

# Submission time Handle Problem Language Result Execution time Memory
846580 2023-09-08T02:34:18 Z LTTrungCHL Growing Trees (BOI11_grow) C++17
10 / 100
 93 ms 5972 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){
        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();
    //}
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 2 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 2832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 2896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4752 KB Output is correct
2 Incorrect 87 ms 5972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 4700 KB Output is correct
2 Incorrect 90 ms 5968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 4944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5140 KB Output is correct