167392025-05-11 22:49:41szilSiklóernyőzéscpp17Időlimit túllépés 38/1002.101s22348 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 v) {
            mx  += v;
            lazy += v;
        }
    };

    int n, h;
    vector<node> tree;

    segtree2() {}
    segtree2(int _n) : n(_n) {
        h = sizeof(int) * 8 - __builtin_clz(n);
        tree.resize(2 * n);
    }

    void apply(int p, int v) {
        tree[p].apply(v);
    }

    void build(int p) {
        while (p > 1) {
            p >>= 1;
            tree[p].mx = max(tree[p<<1].mx, tree[p<<1|1].mx) + tree[p].lazy;
        }
    }

    void push(int p) {
        for (int s = h; s > 0; --s) {
            int i = p >> s;
            if (tree[i].lazy) {
                tree[i<<1].apply(tree[i].lazy);
                tree[i<<1|1].apply(tree[i].lazy);
                tree[i].lazy = 0;
            }
        }
    }

    void upd_add(int a, int b, int c, int l, int r, int v) {
        if (l > r) return;
        int l0 = l += n, r0 = ++r += n;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) apply(l++, v);
            if (r & 1) apply(--r, v);
        }
        build(l0);
        build(r0 - 1);
    }

    int qry(int a, int b, int c, int l, int r) {
        if (l > r) return 0;
        int res = 0;
        int l0 = l += n, r0 = ++r += n;
        push(l0);
        push(r0 - 1);
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, tree[l++].mx);
            if (r & 1) res = max(res, tree[--r].mx);
        }
        return res;
    }
};

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, int u = -1) -> void {
        if (l > r) return;
        if (u == -1) 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, v);
    };

    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.073s12648 KiB
subtask20/5
3Időlimit túllépés2.075s22348 KiB
4Időlimit túllépés2.073s12832 KiB
5Időlimit túllépés2.075s14132 KiB
6Időlimit túllépés2.075s22072 KiB
7Időlimit túllépés2.081s18740 KiB
8Elfogadva252ms20484 KiB
subtask313/13
9Elfogadva2ms564 KiB
10Elfogadva2ms760 KiB
11Elfogadva2ms564 KiB
12Elfogadva2ms564 KiB
13Elfogadva2ms564 KiB
14Elfogadva2ms564 KiB
15Elfogadva2ms564 KiB
16Elfogadva2ms596 KiB
17Elfogadva2ms564 KiB
subtask410/10
18Elfogadva2ms564 KiB
19Elfogadva2ms760 KiB
20Elfogadva2ms564 KiB
21Elfogadva2ms564 KiB
22Elfogadva2ms564 KiB
23Elfogadva2ms564 KiB
24Elfogadva2ms564 KiB
25Elfogadva2ms596 KiB
26Elfogadva2ms564 KiB
27Elfogadva71ms9780 KiB
28Elfogadva68ms9648 KiB
29Elfogadva68ms9792 KiB
30Elfogadva70ms9780 KiB
31Elfogadva70ms9592 KiB
32Elfogadva68ms9808 KiB
33Elfogadva108ms12160 KiB
34Elfogadva114ms12084 KiB
35Elfogadva108ms10548 KiB
36Elfogadva115ms17204 KiB
subtask515/15
37Elfogadva2ms564 KiB
38Elfogadva2ms760 KiB
39Elfogadva2ms564 KiB
40Elfogadva2ms564 KiB
41Elfogadva2ms564 KiB
42Elfogadva2ms564 KiB
43Elfogadva2ms564 KiB
44Elfogadva2ms596 KiB
45Elfogadva2ms564 KiB
46Elfogadva439ms4620 KiB
47Elfogadva463ms4404 KiB
48Elfogadva335ms4412 KiB
49Elfogadva335ms4540 KiB
50Elfogadva1.133s3376 KiB
51Elfogadva1.134s3380 KiB
52Elfogadva1.085s3488 KiB
53Elfogadva1.092s3380 KiB
54Elfogadva442ms4404 KiB
55Elfogadva437ms4404 KiB
56Elfogadva432ms4408 KiB
57Elfogadva423ms4492 KiB
subtask60/10
58Időlimit túllépés2.082s12700 KiB
59Elfogadva1.993s12768 KiB
60Időlimit túllépés2.082s12608 KiB
61Időlimit túllépés2.002s12728 KiB
62Elfogadva1.633s12596 KiB
63Elfogadva1.873s12540 KiB
64Elfogadva247ms16588 KiB
65Elfogadva250ms15924 KiB
66Elfogadva246ms14644 KiB
67Elfogadva243ms16948 KiB
subtask70/11
68Elfogadva2ms564 KiB
69Elfogadva2ms760 KiB
70Elfogadva2ms564 KiB
71Elfogadva2ms564 KiB
72Elfogadva2ms564 KiB
73Elfogadva2ms564 KiB
74Elfogadva2ms564 KiB
75Elfogadva2ms596 KiB
76Elfogadva2ms564 KiB
77Elfogadva71ms9780 KiB
78Elfogadva68ms9648 KiB
79Elfogadva68ms9792 KiB
80Elfogadva70ms9780 KiB
81Elfogadva70ms9592 KiB
82Elfogadva68ms9808 KiB
83Elfogadva108ms12160 KiB
84Elfogadva114ms12084 KiB
85Elfogadva108ms10548 KiB
86Elfogadva115ms17204 KiB
87Időlimit túllépés2.082s12700 KiB
88Elfogadva1.993s12768 KiB
89Időlimit túllépés2.082s12608 KiB
90Időlimit túllépés2.002s12728 KiB
91Elfogadva1.633s12596 KiB
92Elfogadva1.873s12540 KiB
93Elfogadva247ms16588 KiB
94Elfogadva250ms15924 KiB
95Elfogadva246ms14644 KiB
96Elfogadva243ms16948 KiB
97Elfogadva1.889s12592 KiB
98Időlimit túllépés2.078s12608 KiB
99Elfogadva1.934s12596 KiB
100Elfogadva1.922s12596 KiB
101Elfogadva1.993s12596 KiB
102Időlimit túllépés2.035s12732 KiB
103Elfogadva330ms16292 KiB
104Elfogadva337ms15292 KiB
105Elfogadva331ms14644 KiB
106Elfogadva328ms19016 KiB
subtask80/21
107Elfogadva1ms548 KiB
108Időlimit túllépés2.085s12596 KiB
109Időlimit túllépés2.086s12596 KiB
110Időlimit túllépés2.086s12600 KiB
111Időlimit túllépés2.101s12612 KiB
112Időlimit túllépés2.094s12752 KiB
113Időlimit túllépés2.094s12504 KiB
114Időlimit túllépés2.094s12380 KiB
115Elfogadva1.889s12588 KiB
116Elfogadva1.835s12592 KiB
117Elfogadva1.901s12752 KiB
118Elfogadva1.674s12620 KiB
119Időlimit túllépés2.048s12596 KiB
120Elfogadva1.611s12744 KiB
121Időlimit túllépés2.086s12408 KiB
122Időlimit túllépés2.084s12596 KiB
subtask90/15
123Elfogadva1ms548 KiB
124Időlimit túllépés2.085s12596 KiB
125Időlimit túllépés2.075s22348 KiB
126Időlimit túllépés2.073s12832 KiB
127Időlimit túllépés2.075s14132 KiB
128Időlimit túllépés2.075s22072 KiB
129Időlimit túllépés2.081s18740 KiB
130Elfogadva252ms20484 KiB
131Elfogadva2ms564 KiB
132Elfogadva2ms760 KiB
133Elfogadva2ms564 KiB
134Elfogadva2ms564 KiB
135Elfogadva2ms564 KiB
136Elfogadva2ms564 KiB
137Elfogadva2ms564 KiB
138Elfogadva2ms596 KiB
139Elfogadva2ms564 KiB
140Elfogadva71ms9780 KiB
141Elfogadva68ms9648 KiB
142Elfogadva68ms9792 KiB
143Elfogadva70ms9780 KiB
144Elfogadva70ms9592 KiB
145Elfogadva68ms9808 KiB
146Elfogadva108ms12160 KiB
147Elfogadva114ms12084 KiB
148Elfogadva108ms10548 KiB
149Elfogadva115ms17204 KiB
150Elfogadva439ms4620 KiB
151Elfogadva463ms4404 KiB
152Elfogadva335ms4412 KiB
153Elfogadva335ms4540 KiB
154Elfogadva1.133s3376 KiB
155Elfogadva1.134s3380 KiB
156Elfogadva1.085s3488 KiB
157Elfogadva1.092s3380 KiB
158Elfogadva442ms4404 KiB
159Elfogadva437ms4404 KiB
160Elfogadva432ms4408 KiB
161Elfogadva423ms4492 KiB
162Időlimit túllépés2.082s12700 KiB
163Elfogadva1.993s12768 KiB
164Időlimit túllépés2.082s12608 KiB
165Időlimit túllépés2.002s12728 KiB
166Elfogadva1.633s12596 KiB
167Elfogadva1.873s12540 KiB
168Elfogadva247ms16588 KiB
169Elfogadva250ms15924 KiB
170Elfogadva246ms14644 KiB
171Elfogadva243ms16948 KiB
172Elfogadva1.889s12592 KiB
173Időlimit túllépés2.078s12608 KiB
174Elfogadva1.934s12596 KiB
175Elfogadva1.922s12596 KiB
176Elfogadva1.993s12596 KiB
177Időlimit túllépés2.035s12732 KiB
178Elfogadva330ms16292 KiB
179Elfogadva337ms15292 KiB
180Elfogadva331ms14644 KiB
181Elfogadva328ms19016 KiB
182Időlimit túllépés2.086s12596 KiB
183Időlimit túllépés2.086s12600 KiB
184Időlimit túllépés2.101s12612 KiB
185Időlimit túllépés2.094s12752 KiB
186Időlimit túllépés2.094s12504 KiB
187Időlimit túllépés2.094s12380 KiB
188Elfogadva1.889s12588 KiB
189Elfogadva1.835s12592 KiB
190Elfogadva1.901s12752 KiB
191Elfogadva1.674s12620 KiB
192Időlimit túllépés2.048s12596 KiB
193Elfogadva1.611s12744 KiB
194Időlimit túllépés2.086s12408 KiB
195Időlimit túllépés2.084s12596 KiB
196Időlimit túllépés2.084s15392 KiB
197Időlimit túllépés2.084s15156 KiB
198Időlimit túllépés2.084s14880 KiB
199Időlimit túllépés2.084s13916 KiB
200Időlimit túllépés2.086s13908 KiB
201Időlimit túllépés2.086s13544 KiB
202Időlimit túllépés2.086s13108 KiB
203Időlimit túllépés2.086s13016 KiB
204Időlimit túllépés2.085s12856 KiB
205Időlimit túllépés2.085s12984 KiB