167352025-05-11 22:27:59szilSiklóernyőzéscpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Time limit exceeded2.088s34160 KiB
subtask20/5
3Time limit exceeded2.085s44084 KiB
4Time limit exceeded2.085s34868 KiB
5Time limit exceeded2.085s36144 KiB
6Time limit exceeded2.085s44084 KiB
7Time limit exceeded2.089s40756 KiB
8Accepted393ms42480 KiB
subtask313/13
9Accepted3ms820 KiB
10Accepted3ms1016 KiB
11Accepted3ms820 KiB
12Accepted3ms820 KiB
13Accepted3ms820 KiB
14Accepted3ms820 KiB
15Accepted4ms820 KiB
16Accepted3ms820 KiB
17Accepted3ms1012 KiB
subtask410/10
18Accepted3ms820 KiB
19Accepted3ms1016 KiB
20Accepted3ms820 KiB
21Accepted3ms820 KiB
22Accepted3ms820 KiB
23Accepted3ms820 KiB
24Accepted4ms820 KiB
25Accepted3ms820 KiB
26Accepted3ms1012 KiB
27Accepted151ms31540 KiB
28Accepted144ms31716 KiB
29Accepted143ms31556 KiB
30Accepted151ms31596 KiB
31Accepted150ms31540 KiB
32Accepted150ms31540 KiB
33Accepted233ms34036 KiB
34Accepted233ms34084 KiB
35Accepted225ms32300 KiB
36Accepted172ms39220 KiB
subtask50/15
37Accepted3ms820 KiB
38Accepted3ms1016 KiB
39Accepted3ms820 KiB
40Accepted3ms820 KiB
41Accepted3ms820 KiB
42Accepted3ms820 KiB
43Accepted4ms820 KiB
44Accepted3ms820 KiB
45Accepted3ms1012 KiB
46Accepted1.023s4968 KiB
47Accepted1.095s4916 KiB
48Accepted740ms4864 KiB
49Accepted742ms4868 KiB
50Time limit exceeded2.085s3652 KiB
51Time limit exceeded2.088s3636 KiB
52Time limit exceeded2.082s3636 KiB
53Time limit exceeded2.082s3636 KiB
54Accepted1.718s4924 KiB
55Accepted1.644s4832 KiB
56Accepted1.593s4836 KiB
57Accepted1.483s4660 KiB
subtask60/10
58Time limit exceeded2.084s34100 KiB
59Time limit exceeded2.082s34128 KiB
60Time limit exceeded2.085s34204 KiB
61Time limit exceeded2.085s34100 KiB
62Time limit exceeded2.078s34360 KiB
63Time limit exceeded2.081s34244 KiB
64Accepted531ms38416 KiB
65Accepted522ms37684 KiB
66Accepted500ms36660 KiB
67Accepted391ms38888 KiB
subtask70/11
68Accepted3ms820 KiB
69Accepted3ms1016 KiB
70Accepted3ms820 KiB
71Accepted3ms820 KiB
72Accepted3ms820 KiB
73Accepted3ms820 KiB
74Accepted4ms820 KiB
75Accepted3ms820 KiB
76Accepted3ms1012 KiB
77Accepted151ms31540 KiB
78Accepted144ms31716 KiB
79Accepted143ms31556 KiB
80Accepted151ms31596 KiB
81Accepted150ms31540 KiB
82Accepted150ms31540 KiB
83Accepted233ms34036 KiB
84Accepted233ms34084 KiB
85Accepted225ms32300 KiB
86Accepted172ms39220 KiB
87Time limit exceeded2.084s34100 KiB
88Time limit exceeded2.082s34128 KiB
89Time limit exceeded2.085s34204 KiB
90Time limit exceeded2.085s34100 KiB
91Time limit exceeded2.078s34360 KiB
92Time limit exceeded2.081s34244 KiB
93Accepted531ms38416 KiB
94Accepted522ms37684 KiB
95Accepted500ms36660 KiB
96Accepted391ms38888 KiB
97Time limit exceeded2.088s34100 KiB
98Time limit exceeded2.088s34212 KiB
99Time limit exceeded2.091s34100 KiB
100Time limit exceeded2.089s34244 KiB
101Time limit exceeded2.089s34196 KiB
102Time limit exceeded2.089s34388 KiB
103Accepted888ms38404 KiB
104Accepted852ms37304 KiB
105Accepted834ms36660 KiB
106Accepted629ms41012 KiB
subtask80/21
107Accepted1ms500 KiB
108Time limit exceeded2.096s34100 KiB
109Time limit exceeded2.096s34252 KiB
110Time limit exceeded2.096s34100 KiB
111Time limit exceeded2.102s34100 KiB
112Time limit exceeded2.082s34180 KiB
113Time limit exceeded2.084s34096 KiB
114Time limit exceeded2.084s34180 KiB
115Time limit exceeded2.102s34100 KiB
116Time limit exceeded2.086s34100 KiB
117Time limit exceeded2.086s34320 KiB
118Time limit exceeded2.086s34100 KiB
119Time limit exceeded2.102s34112 KiB
120Time limit exceeded2.088s34100 KiB
121Time limit exceeded2.088s34188 KiB
122Time limit exceeded2.088s34104 KiB
subtask90/15
123Accepted1ms500 KiB
124Time limit exceeded2.096s34100 KiB
125Time limit exceeded2.085s44084 KiB
126Time limit exceeded2.085s34868 KiB
127Time limit exceeded2.085s36144 KiB
128Time limit exceeded2.085s44084 KiB
129Time limit exceeded2.089s40756 KiB
130Accepted393ms42480 KiB
131Accepted3ms820 KiB
132Accepted3ms1016 KiB
133Accepted3ms820 KiB
134Accepted3ms820 KiB
135Accepted3ms820 KiB
136Accepted3ms820 KiB
137Accepted4ms820 KiB
138Accepted3ms820 KiB
139Accepted3ms1012 KiB
140Accepted151ms31540 KiB
141Accepted144ms31716 KiB
142Accepted143ms31556 KiB
143Accepted151ms31596 KiB
144Accepted150ms31540 KiB
145Accepted150ms31540 KiB
146Accepted233ms34036 KiB
147Accepted233ms34084 KiB
148Accepted225ms32300 KiB
149Accepted172ms39220 KiB
150Accepted1.023s4968 KiB
151Accepted1.095s4916 KiB
152Accepted740ms4864 KiB
153Accepted742ms4868 KiB
154Time limit exceeded2.085s3652 KiB
155Time limit exceeded2.088s3636 KiB
156Time limit exceeded2.082s3636 KiB
157Time limit exceeded2.082s3636 KiB
158Accepted1.718s4924 KiB
159Accepted1.644s4832 KiB
160Accepted1.593s4836 KiB
161Accepted1.483s4660 KiB
162Time limit exceeded2.084s34100 KiB
163Time limit exceeded2.082s34128 KiB
164Time limit exceeded2.085s34204 KiB
165Time limit exceeded2.085s34100 KiB
166Time limit exceeded2.078s34360 KiB
167Time limit exceeded2.081s34244 KiB
168Accepted531ms38416 KiB
169Accepted522ms37684 KiB
170Accepted500ms36660 KiB
171Accepted391ms38888 KiB
172Time limit exceeded2.088s34100 KiB
173Time limit exceeded2.088s34212 KiB
174Time limit exceeded2.091s34100 KiB
175Time limit exceeded2.089s34244 KiB
176Time limit exceeded2.089s34196 KiB
177Time limit exceeded2.089s34388 KiB
178Accepted888ms38404 KiB
179Accepted852ms37304 KiB
180Accepted834ms36660 KiB
181Accepted629ms41012 KiB
182Time limit exceeded2.096s34252 KiB
183Time limit exceeded2.096s34100 KiB
184Time limit exceeded2.102s34100 KiB
185Time limit exceeded2.082s34180 KiB
186Time limit exceeded2.084s34096 KiB
187Time limit exceeded2.084s34180 KiB
188Time limit exceeded2.102s34100 KiB
189Time limit exceeded2.086s34100 KiB
190Time limit exceeded2.086s34320 KiB
191Time limit exceeded2.086s34100 KiB
192Time limit exceeded2.102s34112 KiB
193Time limit exceeded2.088s34100 KiB
194Time limit exceeded2.088s34188 KiB
195Time limit exceeded2.088s34104 KiB
196Time limit exceeded2.082s37172 KiB
197Time limit exceeded2.082s37100 KiB
198Time limit exceeded2.082s36916 KiB
199Time limit exceeded2.082s35640 KiB
200Time limit exceeded2.096s35636 KiB
201Time limit exceeded2.098s35528 KiB
202Time limit exceeded2.098s35064 KiB
203Time limit exceeded2.098s34880 KiB
204Time limit exceeded2.084s34924 KiB
205Time limit exceeded2.084s34856 KiB