167352025-05-11 22:27:59szilSiklóernyőzéscpp17Időlimit túllépés 23/1002.102s44084 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 200'001;
int K;

struct segtree1 {
    vector<pair<int, int>> tree;
    int n;

    segtree1() {}

    segtree1(int n) : n(n) {
        tree.resize(2*n);
    }

    void upd(int u, int k) {
        tree[u + n] = {k, u};
        u += n;
        for (u /= 2; u >= 1; u /= 2) {
            tree[u] = max(tree[2*u], tree[2*u+1]);
        }
    }

    int qry(int l, int r) {
        l += n; r += n;
        pair<int, int> res = {0, 0};
        while (l <= r) {
            if (l % 2 == 1) res = max(res, tree[l++]);
            if (r % 2 == 0) res = max(res, tree[r--]);
            l /= 2; r /= 2;
        }
        return res.second;
    }
};

struct segtree2 {
    struct node {
        int mx = 0, lazy = 0;

        void apply(int x) {
            lazy += x;
        }
    };

    vector<node> tree;
    int n;

    segtree2() {}

    segtree2(int n) : n(n) {
        tree.resize(16*n);
    }

    void push(int v) {

        node &u = tree[v];
        node &l = tree[2*v];
        node &r = tree[2*v+1];
        u.mx += u.lazy;
        l.apply(u.lazy);
        r.apply(u.lazy);
        u.lazy = 0;
    }

    void pull(int v) {

        push(v);
        push(2*v);
        push(2*v+1);

        node &u = tree[v];
        node &l = tree[2*v];
        node &r = tree[2*v+1];

        u.mx = max(l.mx, r.mx);
    }

    void upd_add(int v, int tl, int tr, int l, int r, int val) {
        if (l > r) return;
        if (l == tl && r == tr) {
            tree[v].apply(val);
        } else {
            int tm = (tl + tr) / 2;
            upd_add(2*v, tl, tm, l, min(r, tm), val);
            upd_add(2*v+1, tm+1, tr, max(l, tm+1), r, val);
            pull(v);
        }
    }

    int qry(int v, int tl, int tr, int l, int r) {
        if (l > r) return 0;
        pull(v);
        if (l == tl && r == tr) {
            return tree[v].mx;
        } else {
            int tm = (tl + tr) / 2;
            return max(qry(2*v, tl, tm, l, min(r, tm)), qry(2*v+1, tm+1, tr, max(tm+1, l), r));
        }
    }
};

int a[MAXN], n, q, il[MAXN], ir[MAXN], ans[MAXN], depth[MAXN], max_depth = 0;
segtree1 st_max;
segtree2 st_depth;

void calc_depth(int l, int r, int d = 0) {
    if (l > r) return;
    int u = st_max.qry(l, r);
    depth[u] = d;
    max_depth = max(max_depth, d);
    il[u] = l;
    ir[u] = r;
    calc_depth(l, u-1, d+1);
    calc_depth(u+1, r, d+1);
}

void rem(int idx) {
    st_depth.upd_add(1, 1, n, il[idx], ir[idx], -1);
}

void add(int idx) {
    st_depth.upd_add(1, 1, n, il[idx], ir[idx], 1);
}

void solve() {
    cin >> n >> q;
    K = sqrt(n);
    for (int i = 1; i <= n; i++) cin >> a[i];
    st_max = segtree1(n+1);
    st_depth = segtree2(n+1);
    for (int i = 1; i <= n; i++) st_max.upd(i, a[i]);
    calc_depth(1, n);
    bool is_subtask7 = max_depth <= 70;
    vector<array<int, 3>> qrys(q);
    auto upd = [&](auto &&self, int l, int r, bool go_right, int sgn) -> void {
        if (l > r) return;
        int u = st_max.qry(l, r);
        int nl = l, nr = r;
        if (go_right) nl = u+1;
        else nr = u-1;
        int v = st_max.qry(nl, nr);
        int outside = depth[v] - depth[u] - 1;
        st_depth.upd_add(1, 1, n, nl, nr, outside * sgn);
        self(self, nl, nr, go_right, sgn);
    };

    if (is_subtask7) {
        for (int i = 1; i <= n; i++) st_depth.upd_add(1, 1, n, i, i, depth[i]);
    }

    for (int i = 0; i < q; i++) {
        if (is_subtask7) {
            int l, r; cin >> l >> r;
            upd(upd, l, r, 0, -1);
            upd(upd, l, r, 1, -1);
            cout << st_depth.qry(1, 1, n, l, r)-depth[st_max.qry(l, r)] << "\n";
            upd(upd, l, r, 0, 1);
            upd(upd, l, r, 1, 1);
        } else {
            cin >> qrys[i][0] >> qrys[i][1];
            qrys[i][2] = i+1;
        }
    }
    if (is_subtask7) return;
    sort(qrys.begin(), qrys.end(), [&](auto a, auto b){
        if (a[0] / K == b[0] / K) return a[1] > b[1];
        return a[0] < b[0];
    });
    int l = 1, r = 0;
    for (auto [nl, nr, idx] : qrys) {
        while (r < nr) add(++r);
        while (l > nl) add(--l);
        while (r > nr) rem(r--);
        while (l < nl) rem(l++);
        ans[idx] = st_depth.qry(1, 1, n, l, r)-1;
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; 
    // cin >> t;
    while (t--) solve();
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Időlimit túllépés2.088s34160 KiB
subtask20/5
3Időlimit túllépés2.085s44084 KiB
4Időlimit túllépés2.085s34868 KiB
5Időlimit túllépés2.085s36144 KiB
6Időlimit túllépés2.085s44084 KiB
7Időlimit túllépés2.089s40756 KiB
8Elfogadva393ms42480 KiB
subtask313/13
9Elfogadva3ms820 KiB
10Elfogadva3ms1016 KiB
11Elfogadva3ms820 KiB
12Elfogadva3ms820 KiB
13Elfogadva3ms820 KiB
14Elfogadva3ms820 KiB
15Elfogadva4ms820 KiB
16Elfogadva3ms820 KiB
17Elfogadva3ms1012 KiB
subtask410/10
18Elfogadva3ms820 KiB
19Elfogadva3ms1016 KiB
20Elfogadva3ms820 KiB
21Elfogadva3ms820 KiB
22Elfogadva3ms820 KiB
23Elfogadva3ms820 KiB
24Elfogadva4ms820 KiB
25Elfogadva3ms820 KiB
26Elfogadva3ms1012 KiB
27Elfogadva151ms31540 KiB
28Elfogadva144ms31716 KiB
29Elfogadva143ms31556 KiB
30Elfogadva151ms31596 KiB
31Elfogadva150ms31540 KiB
32Elfogadva150ms31540 KiB
33Elfogadva233ms34036 KiB
34Elfogadva233ms34084 KiB
35Elfogadva225ms32300 KiB
36Elfogadva172ms39220 KiB
subtask50/15
37Elfogadva3ms820 KiB
38Elfogadva3ms1016 KiB
39Elfogadva3ms820 KiB
40Elfogadva3ms820 KiB
41Elfogadva3ms820 KiB
42Elfogadva3ms820 KiB
43Elfogadva4ms820 KiB
44Elfogadva3ms820 KiB
45Elfogadva3ms1012 KiB
46Elfogadva1.023s4968 KiB
47Elfogadva1.095s4916 KiB
48Elfogadva740ms4864 KiB
49Elfogadva742ms4868 KiB
50Időlimit túllépés2.085s3652 KiB
51Időlimit túllépés2.088s3636 KiB
52Időlimit túllépés2.082s3636 KiB
53Időlimit túllépés2.082s3636 KiB
54Elfogadva1.718s4924 KiB
55Elfogadva1.644s4832 KiB
56Elfogadva1.593s4836 KiB
57Elfogadva1.483s4660 KiB
subtask60/10
58Időlimit túllépés2.084s34100 KiB
59Időlimit túllépés2.082s34128 KiB
60Időlimit túllépés2.085s34204 KiB
61Időlimit túllépés2.085s34100 KiB
62Időlimit túllépés2.078s34360 KiB
63Időlimit túllépés2.081s34244 KiB
64Elfogadva531ms38416 KiB
65Elfogadva522ms37684 KiB
66Elfogadva500ms36660 KiB
67Elfogadva391ms38888 KiB
subtask70/11
68Elfogadva3ms820 KiB
69Elfogadva3ms1016 KiB
70Elfogadva3ms820 KiB
71Elfogadva3ms820 KiB
72Elfogadva3ms820 KiB
73Elfogadva3ms820 KiB
74Elfogadva4ms820 KiB
75Elfogadva3ms820 KiB
76Elfogadva3ms1012 KiB
77Elfogadva151ms31540 KiB
78Elfogadva144ms31716 KiB
79Elfogadva143ms31556 KiB
80Elfogadva151ms31596 KiB
81Elfogadva150ms31540 KiB
82Elfogadva150ms31540 KiB
83Elfogadva233ms34036 KiB
84Elfogadva233ms34084 KiB
85Elfogadva225ms32300 KiB
86Elfogadva172ms39220 KiB
87Időlimit túllépés2.084s34100 KiB
88Időlimit túllépés2.082s34128 KiB
89Időlimit túllépés2.085s34204 KiB
90Időlimit túllépés2.085s34100 KiB
91Időlimit túllépés2.078s34360 KiB
92Időlimit túllépés2.081s34244 KiB
93Elfogadva531ms38416 KiB
94Elfogadva522ms37684 KiB
95Elfogadva500ms36660 KiB
96Elfogadva391ms38888 KiB
97Időlimit túllépés2.088s34100 KiB
98Időlimit túllépés2.088s34212 KiB
99Időlimit túllépés2.091s34100 KiB
100Időlimit túllépés2.089s34244 KiB
101Időlimit túllépés2.089s34196 KiB
102Időlimit túllépés2.089s34388 KiB
103Elfogadva888ms38404 KiB
104Elfogadva852ms37304 KiB
105Elfogadva834ms36660 KiB
106Elfogadva629ms41012 KiB
subtask80/21
107Elfogadva1ms500 KiB
108Időlimit túllépés2.096s34100 KiB
109Időlimit túllépés2.096s34252 KiB
110Időlimit túllépés2.096s34100 KiB
111Időlimit túllépés2.102s34100 KiB
112Időlimit túllépés2.082s34180 KiB
113Időlimit túllépés2.084s34096 KiB
114Időlimit túllépés2.084s34180 KiB
115Időlimit túllépés2.102s34100 KiB
116Időlimit túllépés2.086s34100 KiB
117Időlimit túllépés2.086s34320 KiB
118Időlimit túllépés2.086s34100 KiB
119Időlimit túllépés2.102s34112 KiB
120Időlimit túllépés2.088s34100 KiB
121Időlimit túllépés2.088s34188 KiB
122Időlimit túllépés2.088s34104 KiB
subtask90/15
123Elfogadva1ms500 KiB
124Időlimit túllépés2.096s34100 KiB
125Időlimit túllépés2.085s44084 KiB
126Időlimit túllépés2.085s34868 KiB
127Időlimit túllépés2.085s36144 KiB
128Időlimit túllépés2.085s44084 KiB
129Időlimit túllépés2.089s40756 KiB
130Elfogadva393ms42480 KiB
131Elfogadva3ms820 KiB
132Elfogadva3ms1016 KiB
133Elfogadva3ms820 KiB
134Elfogadva3ms820 KiB
135Elfogadva3ms820 KiB
136Elfogadva3ms820 KiB
137Elfogadva4ms820 KiB
138Elfogadva3ms820 KiB
139Elfogadva3ms1012 KiB
140Elfogadva151ms31540 KiB
141Elfogadva144ms31716 KiB
142Elfogadva143ms31556 KiB
143Elfogadva151ms31596 KiB
144Elfogadva150ms31540 KiB
145Elfogadva150ms31540 KiB
146Elfogadva233ms34036 KiB
147Elfogadva233ms34084 KiB
148Elfogadva225ms32300 KiB
149Elfogadva172ms39220 KiB
150Elfogadva1.023s4968 KiB
151Elfogadva1.095s4916 KiB
152Elfogadva740ms4864 KiB
153Elfogadva742ms4868 KiB
154Időlimit túllépés2.085s3652 KiB
155Időlimit túllépés2.088s3636 KiB
156Időlimit túllépés2.082s3636 KiB
157Időlimit túllépés2.082s3636 KiB
158Elfogadva1.718s4924 KiB
159Elfogadva1.644s4832 KiB
160Elfogadva1.593s4836 KiB
161Elfogadva1.483s4660 KiB
162Időlimit túllépés2.084s34100 KiB
163Időlimit túllépés2.082s34128 KiB
164Időlimit túllépés2.085s34204 KiB
165Időlimit túllépés2.085s34100 KiB
166Időlimit túllépés2.078s34360 KiB
167Időlimit túllépés2.081s34244 KiB
168Elfogadva531ms38416 KiB
169Elfogadva522ms37684 KiB
170Elfogadva500ms36660 KiB
171Elfogadva391ms38888 KiB
172Időlimit túllépés2.088s34100 KiB
173Időlimit túllépés2.088s34212 KiB
174Időlimit túllépés2.091s34100 KiB
175Időlimit túllépés2.089s34244 KiB
176Időlimit túllépés2.089s34196 KiB
177Időlimit túllépés2.089s34388 KiB
178Elfogadva888ms38404 KiB
179Elfogadva852ms37304 KiB
180Elfogadva834ms36660 KiB
181Elfogadva629ms41012 KiB
182Időlimit túllépés2.096s34252 KiB
183Időlimit túllépés2.096s34100 KiB
184Időlimit túllépés2.102s34100 KiB
185Időlimit túllépés2.082s34180 KiB
186Időlimit túllépés2.084s34096 KiB
187Időlimit túllépés2.084s34180 KiB
188Időlimit túllépés2.102s34100 KiB
189Időlimit túllépés2.086s34100 KiB
190Időlimit túllépés2.086s34320 KiB
191Időlimit túllépés2.086s34100 KiB
192Időlimit túllépés2.102s34112 KiB
193Időlimit túllépés2.088s34100 KiB
194Időlimit túllépés2.088s34188 KiB
195Időlimit túllépés2.088s34104 KiB
196Időlimit túllépés2.082s37172 KiB
197Időlimit túllépés2.082s37100 KiB
198Időlimit túllépés2.082s36916 KiB
199Időlimit túllépés2.082s35640 KiB
200Időlimit túllépés2.096s35636 KiB
201Időlimit túllépés2.098s35528 KiB
202Időlimit túllépés2.098s35064 KiB
203Időlimit túllépés2.098s34880 KiB
204Időlimit túllépés2.084s34924 KiB
205Időlimit túllépés2.084s34856 KiB