167302025-05-11 21:51:07szilSiklóernyőzéscpp17Runtime error 23/100375ms37612 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 200'001;
const int K = 400;

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;

    segtree2() {}

    segtree2(int n) {
        tree.resize(8*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];
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);
    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;
    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);
    vector<array<int, 3>> qrys(q);
    for (int i = 0; i < q; i++) {
        cin >> qrys[i][0] >> qrys[i][1];
        qrys[i][2] = i+1;
    }
    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
1Accepted1ms352 KiB
2Runtime error261ms25096 KiB
subtask20/5
3Runtime error287ms37612 KiB
4Runtime error268ms25140 KiB
5Runtime error266ms26676 KiB
6Runtime error282ms37588 KiB
7Runtime error270ms33036 KiB
8Runtime error248ms32368 KiB
subtask313/13
9Accepted3ms752 KiB
10Accepted3ms564 KiB
11Accepted3ms564 KiB
12Accepted3ms564 KiB
13Accepted3ms564 KiB
14Accepted3ms564 KiB
15Accepted4ms564 KiB
16Accepted3ms564 KiB
17Accepted3ms820 KiB
subtask410/10
18Accepted3ms752 KiB
19Accepted3ms564 KiB
20Accepted3ms564 KiB
21Accepted3ms564 KiB
22Accepted3ms564 KiB
23Accepted3ms564 KiB
24Accepted4ms564 KiB
25Accepted3ms564 KiB
26Accepted3ms820 KiB
27Accepted145ms19588 KiB
28Accepted145ms19508 KiB
29Accepted142ms19508 KiB
30Accepted142ms19540 KiB
31Accepted145ms19508 KiB
32Accepted145ms19508 KiB
33Accepted226ms23020 KiB
34Accepted224ms22784 KiB
35Accepted216ms20532 KiB
36Accepted170ms29748 KiB
subtask50/15
37Accepted3ms752 KiB
38Accepted3ms564 KiB
39Accepted3ms564 KiB
40Accepted3ms564 KiB
41Accepted3ms564 KiB
42Accepted3ms564 KiB
43Accepted4ms564 KiB
44Accepted3ms564 KiB
45Accepted3ms820 KiB
46Runtime error79ms5424 KiB
47Runtime error79ms4916 KiB
48Runtime error78ms4916 KiB
49Runtime error75ms4916 KiB
50Runtime error79ms5112 KiB
51Runtime error79ms4984 KiB
52Runtime error79ms5172 KiB
53Runtime error79ms4984 KiB
54Runtime error81ms5184 KiB
55Runtime error81ms5172 KiB
56Runtime error79ms5116 KiB
57Runtime error79ms4992 KiB
subtask60/10
58Runtime error237ms23860 KiB
59Runtime error231ms23860 KiB
60Runtime error234ms23860 KiB
61Runtime error231ms24072 KiB
62Runtime error231ms23912 KiB
63Runtime error237ms23840 KiB
64Runtime error337ms26932 KiB
65Runtime error324ms26204 KiB
66Runtime error312ms24824 KiB
67Runtime error248ms27700 KiB
subtask70/11
68Accepted3ms752 KiB
69Accepted3ms564 KiB
70Accepted3ms564 KiB
71Accepted3ms564 KiB
72Accepted3ms564 KiB
73Accepted3ms564 KiB
74Accepted4ms564 KiB
75Accepted3ms564 KiB
76Accepted3ms820 KiB
77Accepted145ms19588 KiB
78Accepted145ms19508 KiB
79Accepted142ms19508 KiB
80Accepted142ms19540 KiB
81Accepted145ms19508 KiB
82Accepted145ms19508 KiB
83Accepted226ms23020 KiB
84Accepted224ms22784 KiB
85Accepted216ms20532 KiB
86Accepted170ms29748 KiB
87Runtime error237ms23860 KiB
88Runtime error231ms23860 KiB
89Runtime error234ms23860 KiB
90Runtime error231ms24072 KiB
91Runtime error231ms23912 KiB
92Runtime error237ms23840 KiB
93Runtime error337ms26932 KiB
94Runtime error324ms26204 KiB
95Runtime error312ms24824 KiB
96Runtime error248ms27700 KiB
97Runtime error187ms24628 KiB
98Runtime error187ms24628 KiB
99Runtime error182ms24628 KiB
100Runtime error181ms24508 KiB
101Runtime error186ms24628 KiB
102Runtime error180ms24628 KiB
103Runtime error254ms27700 KiB
104Runtime error244ms26252 KiB
105Runtime error237ms25396 KiB
106Runtime error201ms31284 KiB
subtask80/21
107Accepted1ms316 KiB
108Runtime error261ms21300 KiB
109Runtime error259ms25064 KiB
110Runtime error257ms24884 KiB
111Runtime error264ms25140 KiB
112Runtime error261ms25052 KiB
113Runtime error259ms25140 KiB
114Runtime error263ms25140 KiB
115Runtime error234ms23920 KiB
116Runtime error236ms23860 KiB
117Runtime error234ms23848 KiB
118Runtime error240ms23860 KiB
119Runtime error239ms23840 KiB
120Runtime error234ms23980 KiB
121Runtime error261ms25140 KiB
122Runtime error263ms24884 KiB
subtask90/15
123Accepted1ms316 KiB
124Runtime error261ms21300 KiB
125Runtime error287ms37612 KiB
126Runtime error268ms25140 KiB
127Runtime error266ms26676 KiB
128Runtime error282ms37588 KiB
129Runtime error270ms33036 KiB
130Runtime error248ms32368 KiB
131Accepted3ms752 KiB
132Accepted3ms564 KiB
133Accepted3ms564 KiB
134Accepted3ms564 KiB
135Accepted3ms564 KiB
136Accepted3ms564 KiB
137Accepted4ms564 KiB
138Accepted3ms564 KiB
139Accepted3ms820 KiB
140Accepted145ms19588 KiB
141Accepted145ms19508 KiB
142Accepted142ms19508 KiB
143Accepted142ms19540 KiB
144Accepted145ms19508 KiB
145Accepted145ms19508 KiB
146Accepted226ms23020 KiB
147Accepted224ms22784 KiB
148Accepted216ms20532 KiB
149Accepted170ms29748 KiB
150Runtime error79ms5424 KiB
151Runtime error79ms4916 KiB
152Runtime error78ms4916 KiB
153Runtime error75ms4916 KiB
154Runtime error79ms5112 KiB
155Runtime error79ms4984 KiB
156Runtime error79ms5172 KiB
157Runtime error79ms4984 KiB
158Runtime error81ms5184 KiB
159Runtime error81ms5172 KiB
160Runtime error79ms5116 KiB
161Runtime error79ms4992 KiB
162Runtime error237ms23860 KiB
163Runtime error231ms23860 KiB
164Runtime error234ms23860 KiB
165Runtime error231ms24072 KiB
166Runtime error231ms23912 KiB
167Runtime error237ms23840 KiB
168Runtime error337ms26932 KiB
169Runtime error324ms26204 KiB
170Runtime error312ms24824 KiB
171Runtime error248ms27700 KiB
172Runtime error187ms24628 KiB
173Runtime error187ms24628 KiB
174Runtime error182ms24628 KiB
175Runtime error181ms24508 KiB
176Runtime error186ms24628 KiB
177Runtime error180ms24628 KiB
178Runtime error254ms27700 KiB
179Runtime error244ms26252 KiB
180Runtime error237ms25396 KiB
181Runtime error201ms31284 KiB
182Runtime error259ms25064 KiB
183Runtime error257ms24884 KiB
184Runtime error264ms25140 KiB
185Runtime error261ms25052 KiB
186Runtime error259ms25140 KiB
187Runtime error263ms25140 KiB
188Runtime error234ms23920 KiB
189Runtime error236ms23860 KiB
190Runtime error234ms23848 KiB
191Runtime error240ms23860 KiB
192Runtime error239ms23840 KiB
193Runtime error234ms23980 KiB
194Runtime error261ms25140 KiB
195Runtime error263ms24884 KiB
196Runtime error368ms28208 KiB
197Runtime error370ms28212 KiB
198Runtime error375ms27780 KiB
199Runtime error356ms26420 KiB
200Runtime error351ms26164 KiB
201Runtime error349ms25928 KiB
202Runtime error340ms25512 KiB
203Runtime error342ms25316 KiB
204Runtime error321ms25140 KiB
205Runtime error317ms25148 KiB