oj.uz

Submission #682129

# Submission time Handle Problem Language Result Execution time Memory
682129 2023-01-15T21:13:16 Z SOCIOPATE Growing Trees (BOI11_grow) C++17
0 / 100
 117 ms 7708 KB 
#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define pll pair<ll, ll>
#define pii pair<int, int>
#define pdd pair<ld, ld>
#define ff first
#define ss second
#define all(v) v.begin(),v.end()

typedef tree<
    pii,
    null_type,
    less<pii>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordset;

#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")

ll INF = 4e18;
const ll mod = 1000000007;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll binpow(ll n, ll m){
    if(m == 0) return 1ll;
    if(m & 1ll) return (n * binpow(n, m - 1ll)) % mod;
    ll b = binpow(n, m / 2ll);
    return (b*b) % mod;
}

ll a[100005], tmin[400005], tmax[400005], tadd[400005] = {0};

void build(int v, int l, int r){
    if(l == r - 1){
        tmin[v] = tmax[v] = a[l];
        return;
    }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1,m, r);
    tmin[v] = min(tmin[2 * v], tmin[2 * v + 1]);
    tmax[v] = max(tmax[2 * v], tmax[2 * v + 1]);
}

void push(int v){
    if(!tadd[v]) return;
    tadd[2 * v] += tadd[v];
    tadd[2 * v + 1] += tadd[v];
    tmin[2 * v] += tadd[v];
    tmax[2 * v] += tadd[v];
    tmin[2 * v + 1] += tadd[v];
    tmax[2 * v + 1] += tadd[v];
    tadd[v] = 0;
}

void upd(int v, int l, int r, int askl, int askr, ll val){
    if(l >= askl && r <= askr){
        tadd[v] += val;
        tmin[v] += val;
        tmax[v] += val;
        return;
    }
    if(l >= askr || r <= askl) return;
    push(v);
    int m = (l + r) / 2;
    upd(2 * v, l, m, askl, askr, val);
    upd(2 * v + 1, m, r, askl, askr, val);
    tmin[v] = min(tmin[2 * v], tmin[2 * v + 1]);
    tmax[v] = max(tmax[2 * v], tmax[2 * v + 1]);
}

ll get(int v, int l, int r, int pos){
    if(l == r - 1) return tmin[v];
    push(v);
    int m = (l + r) / 2;
    if(pos < m) return get(2 * v, l, m, pos);
    else return get(2 * v + 1, m, r, pos);
}

int posleft(int v, int l, int r, int val){
    if(l == r - 1) return l;
    push(v);
    int m = (l + r) / 2;
    if(tmax[2 * v] < val) return posleft(2 * v + 1, m, r, val);
    else return posleft(2 * v, l, m, val);
}

int posright(int v, int l, int r, int val){
    if(l == r - 1) return l;
    push(v);
    int m = (l + r) / 2;
    if(tmin[2 * v + 1] > val) return posright(2 * v, l, m, val);
    else return posright(2 * v + 1, m, r, val);
}

void printtree(int v, int l, int r){
    if(l == r - 1) {
        cout << tmin[v] << ' ';
        return;
    }
    push(v);
    int m = (l + r) / 2;
    printtree(2 * v, l, m);
    printtree(2 * v + 1, m, r);
}

void solve(){
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    build(1, 0, n);
    for(int i = 0; i < q; i++){
        char c;
        ll l, r;
        cin >> c >> l >> r;
        if(c == 'F'){
            if(r > get(1, 0, n, n - 1)) continue;
            int posst = posleft(1, 0, n, r);
            ll val = get(1, 0, n, posst + l - 1);
            int posl = posleft(1, 0, n, val);
            int posr = posright(1, 0, n, val);
            //cout << posst << ' ' << val << ' ' << posl << ' ' << posr << '\n';
            if(posst == posl){
                upd(1, 0, n, posr - l + 1, posr + 1, 1);
                continue;
            }
            upd(1, 0, n, posst, posl, 1);
            int ost = l - (posl - posst);
            upd(1, 0, n, posr - ost + 1, posr + 1, 1);
        } else {
            int posl = posleft(1, 0, n, l);
            int posr = posright(1, 0, n, r);
            if(get(1, 0, n, posr) < l || get(1, 0, n, posl) > r) {
                cout << 0 << '\n';
                continue;
            }
            cout << posr - posl + 1 << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #endif
	int tt;
    //cin >> tt;
    tt = 1;
    while(tt--){
        solve();
		#ifdef LOCAL
            cout << "__________________________________" << endl;
		#endif
	}
	#ifdef LOCAL
        cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << "sec" << '\n';
	#endif
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 7236 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 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Incorrect 2 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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