167302025-05-11 21:51:07szilSiklóernyőzéscpp17Futási hiba 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms352 KiB
2Futási hiba261ms25096 KiB
subtask20/5
3Futási hiba287ms37612 KiB
4Futási hiba268ms25140 KiB
5Futási hiba266ms26676 KiB
6Futási hiba282ms37588 KiB
7Futási hiba270ms33036 KiB
8Futási hiba248ms32368 KiB
subtask313/13
9Elfogadva3ms752 KiB
10Elfogadva3ms564 KiB
11Elfogadva3ms564 KiB
12Elfogadva3ms564 KiB
13Elfogadva3ms564 KiB
14Elfogadva3ms564 KiB
15Elfogadva4ms564 KiB
16Elfogadva3ms564 KiB
17Elfogadva3ms820 KiB
subtask410/10
18Elfogadva3ms752 KiB
19Elfogadva3ms564 KiB
20Elfogadva3ms564 KiB
21Elfogadva3ms564 KiB
22Elfogadva3ms564 KiB
23Elfogadva3ms564 KiB
24Elfogadva4ms564 KiB
25Elfogadva3ms564 KiB
26Elfogadva3ms820 KiB
27Elfogadva145ms19588 KiB
28Elfogadva145ms19508 KiB
29Elfogadva142ms19508 KiB
30Elfogadva142ms19540 KiB
31Elfogadva145ms19508 KiB
32Elfogadva145ms19508 KiB
33Elfogadva226ms23020 KiB
34Elfogadva224ms22784 KiB
35Elfogadva216ms20532 KiB
36Elfogadva170ms29748 KiB
subtask50/15
37Elfogadva3ms752 KiB
38Elfogadva3ms564 KiB
39Elfogadva3ms564 KiB
40Elfogadva3ms564 KiB
41Elfogadva3ms564 KiB
42Elfogadva3ms564 KiB
43Elfogadva4ms564 KiB
44Elfogadva3ms564 KiB
45Elfogadva3ms820 KiB
46Futási hiba79ms5424 KiB
47Futási hiba79ms4916 KiB
48Futási hiba78ms4916 KiB
49Futási hiba75ms4916 KiB
50Futási hiba79ms5112 KiB
51Futási hiba79ms4984 KiB
52Futási hiba79ms5172 KiB
53Futási hiba79ms4984 KiB
54Futási hiba81ms5184 KiB
55Futási hiba81ms5172 KiB
56Futási hiba79ms5116 KiB
57Futási hiba79ms4992 KiB
subtask60/10
58Futási hiba237ms23860 KiB
59Futási hiba231ms23860 KiB
60Futási hiba234ms23860 KiB
61Futási hiba231ms24072 KiB
62Futási hiba231ms23912 KiB
63Futási hiba237ms23840 KiB
64Futási hiba337ms26932 KiB
65Futási hiba324ms26204 KiB
66Futási hiba312ms24824 KiB
67Futási hiba248ms27700 KiB
subtask70/11
68Elfogadva3ms752 KiB
69Elfogadva3ms564 KiB
70Elfogadva3ms564 KiB
71Elfogadva3ms564 KiB
72Elfogadva3ms564 KiB
73Elfogadva3ms564 KiB
74Elfogadva4ms564 KiB
75Elfogadva3ms564 KiB
76Elfogadva3ms820 KiB
77Elfogadva145ms19588 KiB
78Elfogadva145ms19508 KiB
79Elfogadva142ms19508 KiB
80Elfogadva142ms19540 KiB
81Elfogadva145ms19508 KiB
82Elfogadva145ms19508 KiB
83Elfogadva226ms23020 KiB
84Elfogadva224ms22784 KiB
85Elfogadva216ms20532 KiB
86Elfogadva170ms29748 KiB
87Futási hiba237ms23860 KiB
88Futási hiba231ms23860 KiB
89Futási hiba234ms23860 KiB
90Futási hiba231ms24072 KiB
91Futási hiba231ms23912 KiB
92Futási hiba237ms23840 KiB
93Futási hiba337ms26932 KiB
94Futási hiba324ms26204 KiB
95Futási hiba312ms24824 KiB
96Futási hiba248ms27700 KiB
97Futási hiba187ms24628 KiB
98Futási hiba187ms24628 KiB
99Futási hiba182ms24628 KiB
100Futási hiba181ms24508 KiB
101Futási hiba186ms24628 KiB
102Futási hiba180ms24628 KiB
103Futási hiba254ms27700 KiB
104Futási hiba244ms26252 KiB
105Futási hiba237ms25396 KiB
106Futási hiba201ms31284 KiB
subtask80/21
107Elfogadva1ms316 KiB
108Futási hiba261ms21300 KiB
109Futási hiba259ms25064 KiB
110Futási hiba257ms24884 KiB
111Futási hiba264ms25140 KiB
112Futási hiba261ms25052 KiB
113Futási hiba259ms25140 KiB
114Futási hiba263ms25140 KiB
115Futási hiba234ms23920 KiB
116Futási hiba236ms23860 KiB
117Futási hiba234ms23848 KiB
118Futási hiba240ms23860 KiB
119Futási hiba239ms23840 KiB
120Futási hiba234ms23980 KiB
121Futási hiba261ms25140 KiB
122Futási hiba263ms24884 KiB
subtask90/15
123Elfogadva1ms316 KiB
124Futási hiba261ms21300 KiB
125Futási hiba287ms37612 KiB
126Futási hiba268ms25140 KiB
127Futási hiba266ms26676 KiB
128Futási hiba282ms37588 KiB
129Futási hiba270ms33036 KiB
130Futási hiba248ms32368 KiB
131Elfogadva3ms752 KiB
132Elfogadva3ms564 KiB
133Elfogadva3ms564 KiB
134Elfogadva3ms564 KiB
135Elfogadva3ms564 KiB
136Elfogadva3ms564 KiB
137Elfogadva4ms564 KiB
138Elfogadva3ms564 KiB
139Elfogadva3ms820 KiB
140Elfogadva145ms19588 KiB
141Elfogadva145ms19508 KiB
142Elfogadva142ms19508 KiB
143Elfogadva142ms19540 KiB
144Elfogadva145ms19508 KiB
145Elfogadva145ms19508 KiB
146Elfogadva226ms23020 KiB
147Elfogadva224ms22784 KiB
148Elfogadva216ms20532 KiB
149Elfogadva170ms29748 KiB
150Futási hiba79ms5424 KiB
151Futási hiba79ms4916 KiB
152Futási hiba78ms4916 KiB
153Futási hiba75ms4916 KiB
154Futási hiba79ms5112 KiB
155Futási hiba79ms4984 KiB
156Futási hiba79ms5172 KiB
157Futási hiba79ms4984 KiB
158Futási hiba81ms5184 KiB
159Futási hiba81ms5172 KiB
160Futási hiba79ms5116 KiB
161Futási hiba79ms4992 KiB
162Futási hiba237ms23860 KiB
163Futási hiba231ms23860 KiB
164Futási hiba234ms23860 KiB
165Futási hiba231ms24072 KiB
166Futási hiba231ms23912 KiB
167Futási hiba237ms23840 KiB
168Futási hiba337ms26932 KiB
169Futási hiba324ms26204 KiB
170Futási hiba312ms24824 KiB
171Futási hiba248ms27700 KiB
172Futási hiba187ms24628 KiB
173Futási hiba187ms24628 KiB
174Futási hiba182ms24628 KiB
175Futási hiba181ms24508 KiB
176Futási hiba186ms24628 KiB
177Futási hiba180ms24628 KiB
178Futási hiba254ms27700 KiB
179Futási hiba244ms26252 KiB
180Futási hiba237ms25396 KiB
181Futási hiba201ms31284 KiB
182Futási hiba259ms25064 KiB
183Futási hiba257ms24884 KiB
184Futási hiba264ms25140 KiB
185Futási hiba261ms25052 KiB
186Futási hiba259ms25140 KiB
187Futási hiba263ms25140 KiB
188Futási hiba234ms23920 KiB
189Futási hiba236ms23860 KiB
190Futási hiba234ms23848 KiB
191Futási hiba240ms23860 KiB
192Futási hiba239ms23840 KiB
193Futási hiba234ms23980 KiB
194Futási hiba261ms25140 KiB
195Futási hiba263ms24884 KiB
196Futási hiba368ms28208 KiB
197Futási hiba370ms28212 KiB
198Futási hiba375ms27780 KiB
199Futási hiba356ms26420 KiB
200Futási hiba351ms26164 KiB
201Futási hiba349ms25928 KiB
202Futási hiba340ms25512 KiB
203Futási hiba342ms25316 KiB
204Futási hiba321ms25140 KiB
205Futási hiba317ms25148 KiB