167392025-05-11 22:49:41szilSiklóernyőzéscpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Time limit exceeded2.073s12648 KiB
subtask20/5
3Time limit exceeded2.075s22348 KiB
4Time limit exceeded2.073s12832 KiB
5Time limit exceeded2.075s14132 KiB
6Time limit exceeded2.075s22072 KiB
7Time limit exceeded2.081s18740 KiB
8Accepted252ms20484 KiB
subtask313/13
9Accepted2ms564 KiB
10Accepted2ms760 KiB
11Accepted2ms564 KiB
12Accepted2ms564 KiB
13Accepted2ms564 KiB
14Accepted2ms564 KiB
15Accepted2ms564 KiB
16Accepted2ms596 KiB
17Accepted2ms564 KiB
subtask410/10
18Accepted2ms564 KiB
19Accepted2ms760 KiB
20Accepted2ms564 KiB
21Accepted2ms564 KiB
22Accepted2ms564 KiB
23Accepted2ms564 KiB
24Accepted2ms564 KiB
25Accepted2ms596 KiB
26Accepted2ms564 KiB
27Accepted71ms9780 KiB
28Accepted68ms9648 KiB
29Accepted68ms9792 KiB
30Accepted70ms9780 KiB
31Accepted70ms9592 KiB
32Accepted68ms9808 KiB
33Accepted108ms12160 KiB
34Accepted114ms12084 KiB
35Accepted108ms10548 KiB
36Accepted115ms17204 KiB
subtask515/15
37Accepted2ms564 KiB
38Accepted2ms760 KiB
39Accepted2ms564 KiB
40Accepted2ms564 KiB
41Accepted2ms564 KiB
42Accepted2ms564 KiB
43Accepted2ms564 KiB
44Accepted2ms596 KiB
45Accepted2ms564 KiB
46Accepted439ms4620 KiB
47Accepted463ms4404 KiB
48Accepted335ms4412 KiB
49Accepted335ms4540 KiB
50Accepted1.133s3376 KiB
51Accepted1.134s3380 KiB
52Accepted1.085s3488 KiB
53Accepted1.092s3380 KiB
54Accepted442ms4404 KiB
55Accepted437ms4404 KiB
56Accepted432ms4408 KiB
57Accepted423ms4492 KiB
subtask60/10
58Time limit exceeded2.082s12700 KiB
59Accepted1.993s12768 KiB
60Time limit exceeded2.082s12608 KiB
61Time limit exceeded2.002s12728 KiB
62Accepted1.633s12596 KiB
63Accepted1.873s12540 KiB
64Accepted247ms16588 KiB
65Accepted250ms15924 KiB
66Accepted246ms14644 KiB
67Accepted243ms16948 KiB
subtask70/11
68Accepted2ms564 KiB
69Accepted2ms760 KiB
70Accepted2ms564 KiB
71Accepted2ms564 KiB
72Accepted2ms564 KiB
73Accepted2ms564 KiB
74Accepted2ms564 KiB
75Accepted2ms596 KiB
76Accepted2ms564 KiB
77Accepted71ms9780 KiB
78Accepted68ms9648 KiB
79Accepted68ms9792 KiB
80Accepted70ms9780 KiB
81Accepted70ms9592 KiB
82Accepted68ms9808 KiB
83Accepted108ms12160 KiB
84Accepted114ms12084 KiB
85Accepted108ms10548 KiB
86Accepted115ms17204 KiB
87Time limit exceeded2.082s12700 KiB
88Accepted1.993s12768 KiB
89Time limit exceeded2.082s12608 KiB
90Time limit exceeded2.002s12728 KiB
91Accepted1.633s12596 KiB
92Accepted1.873s12540 KiB
93Accepted247ms16588 KiB
94Accepted250ms15924 KiB
95Accepted246ms14644 KiB
96Accepted243ms16948 KiB
97Accepted1.889s12592 KiB
98Time limit exceeded2.078s12608 KiB
99Accepted1.934s12596 KiB
100Accepted1.922s12596 KiB
101Accepted1.993s12596 KiB
102Time limit exceeded2.035s12732 KiB
103Accepted330ms16292 KiB
104Accepted337ms15292 KiB
105Accepted331ms14644 KiB
106Accepted328ms19016 KiB
subtask80/21
107Accepted1ms548 KiB
108Time limit exceeded2.085s12596 KiB
109Time limit exceeded2.086s12596 KiB
110Time limit exceeded2.086s12600 KiB
111Time limit exceeded2.101s12612 KiB
112Time limit exceeded2.094s12752 KiB
113Time limit exceeded2.094s12504 KiB
114Time limit exceeded2.094s12380 KiB
115Accepted1.889s12588 KiB
116Accepted1.835s12592 KiB
117Accepted1.901s12752 KiB
118Accepted1.674s12620 KiB
119Time limit exceeded2.048s12596 KiB
120Accepted1.611s12744 KiB
121Time limit exceeded2.086s12408 KiB
122Time limit exceeded2.084s12596 KiB
subtask90/15
123Accepted1ms548 KiB
124Time limit exceeded2.085s12596 KiB
125Time limit exceeded2.075s22348 KiB
126Time limit exceeded2.073s12832 KiB
127Time limit exceeded2.075s14132 KiB
128Time limit exceeded2.075s22072 KiB
129Time limit exceeded2.081s18740 KiB
130Accepted252ms20484 KiB
131Accepted2ms564 KiB
132Accepted2ms760 KiB
133Accepted2ms564 KiB
134Accepted2ms564 KiB
135Accepted2ms564 KiB
136Accepted2ms564 KiB
137Accepted2ms564 KiB
138Accepted2ms596 KiB
139Accepted2ms564 KiB
140Accepted71ms9780 KiB
141Accepted68ms9648 KiB
142Accepted68ms9792 KiB
143Accepted70ms9780 KiB
144Accepted70ms9592 KiB
145Accepted68ms9808 KiB
146Accepted108ms12160 KiB
147Accepted114ms12084 KiB
148Accepted108ms10548 KiB
149Accepted115ms17204 KiB
150Accepted439ms4620 KiB
151Accepted463ms4404 KiB
152Accepted335ms4412 KiB
153Accepted335ms4540 KiB
154Accepted1.133s3376 KiB
155Accepted1.134s3380 KiB
156Accepted1.085s3488 KiB
157Accepted1.092s3380 KiB
158Accepted442ms4404 KiB
159Accepted437ms4404 KiB
160Accepted432ms4408 KiB
161Accepted423ms4492 KiB
162Time limit exceeded2.082s12700 KiB
163Accepted1.993s12768 KiB
164Time limit exceeded2.082s12608 KiB
165Time limit exceeded2.002s12728 KiB
166Accepted1.633s12596 KiB
167Accepted1.873s12540 KiB
168Accepted247ms16588 KiB
169Accepted250ms15924 KiB
170Accepted246ms14644 KiB
171Accepted243ms16948 KiB
172Accepted1.889s12592 KiB
173Time limit exceeded2.078s12608 KiB
174Accepted1.934s12596 KiB
175Accepted1.922s12596 KiB
176Accepted1.993s12596 KiB
177Time limit exceeded2.035s12732 KiB
178Accepted330ms16292 KiB
179Accepted337ms15292 KiB
180Accepted331ms14644 KiB
181Accepted328ms19016 KiB
182Time limit exceeded2.086s12596 KiB
183Time limit exceeded2.086s12600 KiB
184Time limit exceeded2.101s12612 KiB
185Time limit exceeded2.094s12752 KiB
186Time limit exceeded2.094s12504 KiB
187Time limit exceeded2.094s12380 KiB
188Accepted1.889s12588 KiB
189Accepted1.835s12592 KiB
190Accepted1.901s12752 KiB
191Accepted1.674s12620 KiB
192Time limit exceeded2.048s12596 KiB
193Accepted1.611s12744 KiB
194Time limit exceeded2.086s12408 KiB
195Time limit exceeded2.084s12596 KiB
196Time limit exceeded2.084s15392 KiB
197Time limit exceeded2.084s15156 KiB
198Time limit exceeded2.084s14880 KiB
199Time limit exceeded2.084s13916 KiB
200Time limit exceeded2.086s13908 KiB
201Time limit exceeded2.086s13544 KiB
202Time limit exceeded2.086s13108 KiB
203Time limit exceeded2.086s13016 KiB
204Time limit exceeded2.085s12856 KiB
205Time limit exceeded2.085s12984 KiB