oj.uz

Submission #689857

# Submission time Handle Problem Language Result Execution time Memory
689857 2023-01-29T14:45:57 Z hafo Growing Trees (BOI11_grow) C++14
0 / 100
 617 ms 4856 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 7;
const ll oo = 1e15 + 69;

int n, a[maxn], u, v, q;
char t;

struct ST {
    int st[4 * maxn], lz[4 * maxn];
    void build(int id, int l, int r) {
        if(l == r) {
            st[id] = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }

    void fix(int id, int l, int r) {
        if(!lz[id]) return;
        if(l == r) st[id] += lz[id];
        else {
            lz[id << 1] += lz[id];
            lz[id << 1 | 1] += lz[id];
        }
        lz[id] = 0;
    }

    void update(int id, int l, int r, int u, int v) {
        fix(id, l, r);
        if(r < u || l > v) return;
        if(u <= l && r <= v) {
            lz[id]++;
            fix(id, l, r);
            return;
        }
        int mid = l + r >> 1;
        update(id << 1, l, mid, u, v);
        update(id << 1 | 1, mid + 1, r, u, v);
    }

    int get(int id, int l, int r, int pos) {
        fix(id, l, r);
        if(r < pos || l > pos) return -1;
        if(l == r) return st[id];
        int mid = l + r >> 1;
        return max(get(id << 1, l, mid, pos), get(id << 1 | 1, mid + 1, r, pos));
    }

    int get(int pos) {
        return get(1, 1, n, pos);
    }
} st;

int bs(int x) {
    int l = 1, r = n, res = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(st.get(mid) >= x) {
            r = mid - 1;
            res = mid;
        } else l = mid + 1;
    }
    return res;
}

int bs2(int x) {
    int l = 1, r = n, res = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(st.get(mid) <= x) {
            l = mid + 1;
            res = mid;
        } else r = mid - 1;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>q;
    for(int i = 1; i <= n; i++) cin>>a[i];
    sort(a + 1, a + 1 + n);
    st.build(1, 1, n);

    while(q--) {
        cin>>t>>u>>v;
        if(t == 'F') {
            int le = bs(v);
            if(le == -1) continue;
            int ri = min(n, le + u - 1), l = bs(st.get(ri)), r = bs2(st.get(ri));
            if(le <= l - 1) st.update(1, 1, n, le, l - 1);
            if(r - u + (l - le) + 1 <= r) st.update(1, 1, n, max(1, r - u + (l - le) + 1), r);
        } else {
            int low = bs(u), high = bs2(v);
            cout<<(low == -1 ? 0:high - low + 1)<<"\n";
        }
    }
    return 0;
}

Compilation message

grow.cpp: In member function 'void ST::build(int, int, int)':
grow.cpp:31:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In member function 'void ST::update(int, int, int, int, int)':
grow.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In member function 'int ST::get(int, int, int, int)':
grow.cpp:63:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In function 'int bs(int)':
grow.cpp:75:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         int mid = l + r >> 1;
      |                   ~~^~~
grow.cpp: In function 'int bs2(int)':
grow.cpp:87:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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