1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void solve() {
    ll n, k;
    cin >> n >> k;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll l = 1, r = a[0] + k, mid, ans;
    auto check = [&](ll mid) -> bool {
        ll cnt = 0;
        rep(i, 0, n - 1) {
            if (a[i] >= mid) continue;
            cnt += (mid - a[i] + i) / (i + 1);
            if (cnt > k) return false;
        }
        return cnt <= k;
    };
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }
    cout << ans << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

void solve() {
    ll n, m, q, x, y;
    cin >> n >> m;
    vector<pll> ma(m);
    map<ll, vector<pll>> ma1;
    map<ll, vector<pll>> ma2;
    map<pll, ll> ma3;
    rep(i, 0, m - 1) {
        cin >> ma[i].first >> ma[i].second;
        ma1[ma[i].first].emplace_back(ma[i].second, i + 1);
        ma2[ma[i].second].emplace_back(ma[i].first, i + 1);
        ma3[ma[i]]++;
    }
    for (auto& [x, y] : ma1) ranges::sort(y);
    for (auto& [x, y] : ma2) ranges::sort(y);
    ranges::sort(ma);
    vl suf1(m + 1, LLONG_MAX), suf2(m + 1, LLONG_MAX);
    frep(i, m - 1, 0) {
        suf1[i] = suf1[i + 1];
        suf2[i] = suf2[i + 1];
        if (ma[i].second <= suf1[i]) {
            suf2[i] = suf1[i];
            suf1[i] = ma[i].second;
        } else if (ma[i].second < suf2[i])
            suf2[i] = ma[i].second;
    }
    cin >> q;
    rep(i, 0, q - 1) {
        cin >> x >> y;
        vector<pll> tem;
        vector<pll> tem2;
        bool flag = false;
        if (ma1.count(x)) {
            auto it = ranges::upper_bound(ma1[x], make_pair(y, LLONG_MAX));
            while (it != ma1[x].begin() && sz(tem) < 2) {
                it--;
                tem.push_back(*it);
            }
        }
        if (ma2.count(y)) {
            auto it = ranges::lower_bound(ma2[y], make_pair(x, -1));
            while (it != ma2[y].end() && sz(tem2) < 2) {
                tem2.push_back(*it);
                it++;
            }
        }
        for (auto& [p, idx1] : tem) {
            for (auto& [q, idx2] : tem2) {
                if (idx1 == idx2) continue;
                if (q <= p + 1) {
                    cout << "Yes" << endl;
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        if (flag) continue;
        if (ma3.count({x, y})) {
            int tem3 = ranges::lower_bound(ma, make_pair(x, -1)) - ma.begin();
            if (tem3 < m && suf2[tem3] <= y) {
                cout << "Yes" << endl;
                flag = true;
                continue;
            }
        }
        if (!flag) cout << "No" << endl;
    }
    return;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

const ll MOD = 998244353;
// 双标记，注意顺序
template <typename T, typename F>
class LazySegmentTree {
    const F TODO_INIT = 0;  // 懒标记初始值
    const F TODO_INIT2 = 1;
    struct Node {
        T val;
        F todo;
        F todo2;
    };
    int n;
    vector<Node> tree;
    T merge_val(const T& a, const T& b) const { return (a + b) % MOD; }                               // 合并两个val
    F merge_todo(const F& a, const F& b, const F& c) const { return (a * c % MOD + b % MOD) % MOD; }  // 合并两个懒标记
    F merge_todo2(const F& a, const F& b) const { return (a * b) % MOD; }                             // 合并两个乘法标记
    void apply(int node, int l, int r, F todo, F todo2) {
        Node& cur = tree[node];
        cur.val *= todo2;
        cur.val %= MOD;
        cur.val += (todo % MOD) * ((r - l + 1) % MOD) % MOD;
        cur.val %= MOD;
        cur.todo = merge_todo(cur.todo, todo, todo2);
        cur.todo2 = merge_todo2(todo2, cur.todo2);
    }  // 把懒标记作用到node子树
    void pushdown(int node, int l, int r) {
        Node& cur = tree[node];
        F todo = cur.todo;
        F todo2 = cur.todo2;
        if (todo == TODO_INIT && todo2 == TODO_INIT2) return;
        int m = (l + r) >> 1;
        apply(node << 1, l, m, todo, todo2);
        apply(node << 1 | 1, m + 1, r, todo, todo2);
        cur.todo = TODO_INIT;
        cur.todo2 = TODO_INIT2;
    }  // 把当前节点的懒标记下传
    void maintain(int node) { tree[node].val = merge_val(tree[node << 1].val, tree[node << 1 | 1].val); }
    // 合并线段树
    void build(const vector<T>& a, int node, int l, int r) {
        Node& cur = tree[node];
        cur.todo = TODO_INIT;
        cur.todo2 = TODO_INIT2;
        if (l == r) {
            cur.val = a[l];
            return;
        }
        int m = (l + r) >> 1;
        build(a, node << 1, l, m);
        build(a, node << 1 | 1, m + 1, r);
        maintain(node);
    }  // 建树，复杂度O(n)
    void update(int node, int l, int r, int ql, int qr, F f) {
        if (ql <= l && r <= qr) {
            apply(node, l, r, f, 1);
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (ql <= m) update(node << 1, l, m, ql, qr, f);
        if (qr > m) update(node << 1 | 1, m + 1, r, ql, qr, f);
        maintain(node);
    }  // 区间更新[ql,qr]
    void update2(int node, int l, int r, int ql, int qr, F f) {
        if (ql <= l && r <= qr) {
            apply(node, l, r, 0, f);
            return;
        }
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (ql <= m) update2(node << 1, l, m, ql, qr, f);
        if (qr > m) update2(node << 1 | 1, m + 1, r, ql, qr, f);
        maintain(node);
    }
    T query(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[node].val;
        pushdown(node, l, r);
        int m = (l + r) >> 1;
        if (qr <= m) return query(node << 1, l, m, ql, qr);
        if (ql > m) return query(node << 1 | 1, m + 1, r, ql, qr);
        T l_res = query(node << 1, l, m, ql, qr) % MOD;
        T r_res = query(node << 1 | 1, m + 1, r, ql, qr) % MOD;
        return merge_val(l_res, r_res);
    }  // 区间查找

public:
    LazySegmentTree(int n, T init_val = 0) : LazySegmentTree(vector<T>(n, init_val)) {}
    // 维护下标为[0,n-1],初始值为init_val的区间，或者数组a
    LazySegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }
    // 更新[ql,qr]为f
    void update(int ql, int qr, F f) { update(1, 0, n - 1, ql, qr, f); }
    // 更新[ql,qr]为f
    void update2(int ql, int qr, F f) { update2(1, 0, n - 1, ql, qr, f); }
    // 区间查询[ql,qr]
    T query(int ql, int qr) { return query(1, 0, n - 1, ql, qr); }
};
void solve() {
    ll n;
    cin >> n;
    vl a(n - 1);
    rep(i, 0, n - 2) cin >> a[i];
    vl tem(n, 0);
    tem[n - 1] = 1;
    LazySegmentTree<ll, ll> tree(tem);
    frep(i, n - 2, 0) {
        ll tem2;
        if (i + a[i] <= n - 1)
            tem2 = tree.query(i + a[i], i + a[i]);
        else
            tem2 = 0;
        if (i <= n - 3 && a[i] == a[i + 1]) {
            tree.update2(0, n - 1, n - i - 2);
        } else {
            tree.update2(0, n - 1, 0);
        }
        if (tem2 > 0) {
            tree.update(i + a[i], i + a[i], tem2);
            tree.update(i, i, tem2);
        }
    }
    cout << tree.query(0, n - 1) % MOD << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void solve() {
    ll n, x, y;
    cin >> n;
    vector<pll> ma(n);
    rep(i, 0, n - 1) {
        cin >> x >> y;
        ma[i].first = x + y;
        ma[i].second = x - y;
    }
    ranges::sort(ma);
    mset<ll> s;
    for (auto& [x, y] : ma) {
        auto it = s.upper_bound(y);
        if (it == s.begin()) {
            s.insert(y);
        } else {
            it--;
            s.erase(it);
            s.insert(y);
        }
    }
    cout << sz(s) << endl;
    return;
}