oj.uz

Submission #524149

# Submission time Handle Problem Language Result Execution time Memory
524149 2022-02-08T17:46:03 Z AA_Surely Growing Trees (BOI11_grow) C++14
100 / 100
 165 ms 9020 KB 
#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(LL i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(LL i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;

typedef long long 		LL;
typedef pair<LL, LL> 	PLL;
typedef vector<LL> 		VLL;
typedef vector<PLL> 	VPLL;

const int MAXN = 1e5 + 7;

LL n, q;
LL ns[MAXN], lazy[MAXN << 2];
PLL tree[MAXN << 2];

inline PLL operator + (const PLL a, const PLL b) {
    return PLL(min(a.F, b.F), max(a.S, b.S));
}

inline PLL operator + (const PLL a, const LL b) {
    return PLL(a.F + b, a.S + b);
}

inline void shift(LL now_on) {
    tree[now_on << 1] = tree[now_on << 1] + lazy[now_on];
    lazy[now_on << 1] += lazy[now_on];

    tree[now_on << 1 | 1] = tree[now_on << 1 | 1] + lazy[now_on];
    lazy[now_on << 1 | 1] += lazy[now_on];
    
    lazy[now_on] = 0;
    return;
}

PLL build(LL now_on = 1, LL ls = 0, LL rs = n - 1) {
    if (ls == rs) return tree[now_on] = PLL(ns[ls], ns[ls]);
    LL mid = (ls + rs) >> 1;
    return tree[now_on] = build(now_on << 1, ls, mid) + build(now_on << 1 | 1, mid + 1, rs);
}

LL lb(LL lq, LL now_on = 1, LL ls = 0, LL rs = n - 1) {
    if (ls == rs) return ls;
    LL mid = (ls + rs) >> 1;
    shift(now_on);
    if (tree[now_on << 1].S >= lq) return lb(lq, now_on << 1, ls, mid);
    return lb(lq, now_on << 1 | 1, mid + 1, rs);
}

LL ub(LL rq, LL now_on = 1, LL ls = 0, LL rs = n - 1) {
    if (ls == rs) return ls;
    LL mid = (ls + rs) >> 1;
    shift(now_on);
    if (tree[now_on << 1 | 1].F <= rq) return ub(rq, now_on << 1 | 1, mid + 1, rs);
    return ub(rq, now_on << 1, ls, mid);
}

LL get(LL id, LL now_on = 1, LL ls = 0, LL rs = n - 1) {
    if (ls == rs) return tree[now_on].F;
    LL mid = (ls + rs) >> 1;
    shift(now_on);
    if (id <= mid) return get(id, now_on << 1, ls, mid);
    return get(id, now_on << 1 | 1, mid + 1, rs);
}

void add(LL lq, LL rq, LL now_on = 1, LL ls = 0, LL rs = n - 1) {
    if (rq < lq || rq < ls || rs < lq) 
        return;

    if (lq <= ls && rs <= rq) {
        tree[now_on] = tree[now_on] + 1;
        lazy[now_on]++;
        return;
    }

    LL mid = (ls + rs) >> 1;
    shift(now_on);
    add(lq, rq, now_on << 1, ls, mid);
    add(lq, rq, now_on << 1 | 1, mid + 1, rs);

    tree[now_on] = tree[now_on << 1] + tree[now_on << 1 | 1];
    return;
}

int main() {
    IOS;
    
    cin >> n >> q;
    F0R(i, n) cin >> ns[i];
    sort(ns, ns + n);
    build();

    while(q--) {
        char tp; cin >> tp;

        if (tp == 'F') {
            LL td, mnm; cin >> td >> mnm;
            if (get(n - 1) < mnm) continue;

            LL st = lb(mnm);
            LL fn = min(n - 1, st + td - 1);

            LL md = get(fn);
            LL smd = lb(md), fmd = ub(md);
            //cout << "adding: " << st << ' ' << smd - 1 << endl;
            add(st, smd - 1);
            add(max(smd, fmd - (td - ((smd - 1) - st + 1)) + 1), fmd);
        }
#define endl '\n'
        else {
            LL mn, mx; cin >> mn >> mx;
            cout << (mx < get(0) || mn > get(n - 1) ? 0 : ub(mx) - lb(mn) + 1) << endl;
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 7424 KB Output is correct
2 Correct 105 ms 8900 KB Output is correct
3 Correct 105 ms 8776 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 39 ms 1732 KB Output is correct
6 Correct 48 ms 1980 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 27 ms 1624 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1196 KB Output is correct
2 Correct 47 ms 2088 KB Output is correct
3 Correct 1 ms 684 KB Output is correct
4 Correct 29 ms 1588 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1220 KB Output is correct
2 Correct 52 ms 2096 KB Output is correct
3 Correct 8 ms 844 KB Output is correct
4 Correct 47 ms 2156 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 4128 KB Output is correct
2 Correct 97 ms 8444 KB Output is correct
3 Correct 15 ms 2372 KB Output is correct
4 Correct 80 ms 8320 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 7236 KB Output is correct
2 Correct 109 ms 8568 KB Output is correct
3 Correct 98 ms 8532 KB Output is correct
4 Correct 14 ms 2380 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 7292 KB Output is correct
2 Correct 75 ms 8444 KB Output is correct
3 Correct 101 ms 8696 KB Output is correct
4 Correct 14 ms 2376 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 7364 KB Output is correct
2 Correct 94 ms 8420 KB Output is correct
3 Correct 28 ms 7916 KB Output is correct
4 Correct 59 ms 8260 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7492 KB Output is correct
2 Correct 95 ms 8752 KB Output is correct
3 Correct 165 ms 9020 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7748 KB Output is correct