oj.uz

Submission #682133

# Submission time Handle Problem Language Result Execution time Memory
682133 2023-01-15T21:24:09 Z SOCIOPATE Growing Trees (BOI11_grow) C++17
100 / 100
 194 ms 9052 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 tmin[400005], tmax[400005], tadd[400005] = {0};
vector<ll> a;

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;
    a.resize(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(all(a));
    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);
            if(posst + l - 1 >= n){
                l = n - posst;
            }
            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, 0) > r || get(1, 0, n, n - 1) < l) {
                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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7348 KB Output is correct
2 Correct 140 ms 8916 KB Output is correct
3 Correct 89 ms 8848 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 42 ms 1744 KB Output is correct
6 Correct 53 ms 2112 KB Output is correct
7 Correct 5 ms 852 KB Output is correct
8 Correct 29 ms 1504 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1124 KB Output is correct
2 Correct 53 ms 2160 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 32 ms 1696 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1208 KB Output is correct
2 Correct 65 ms 2096 KB Output is correct
3 Correct 9 ms 852 KB Output is correct
4 Correct 50 ms 2128 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 4104 KB Output is correct
2 Correct 108 ms 8436 KB Output is correct
3 Correct 14 ms 2516 KB Output is correct
4 Correct 73 ms 8316 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 7156 KB Output is correct
2 Correct 100 ms 8524 KB Output is correct
3 Correct 92 ms 8556 KB Output is correct
4 Correct 15 ms 2396 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 7244 KB Output is correct
2 Correct 73 ms 8560 KB Output is correct
3 Correct 89 ms 8784 KB Output is correct
4 Correct 14 ms 2332 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 7300 KB Output is correct
2 Correct 119 ms 8384 KB Output is correct
3 Correct 31 ms 7968 KB Output is correct
4 Correct 66 ms 8288 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7328 KB Output is correct
2 Correct 103 ms 8780 KB Output is correct
3 Correct 194 ms 9052 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 7752 KB Output is correct