167312025-05-11 21:55:28szilSiklóernyőzéscpp17Időlimit túllépés 44/1002.102s46476 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(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];
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
1Elfogadva1ms316 KiB
2Időlimit túllépés2.088s34100 KiB
subtask20/5
3Időlimit túllépés2.085s46476 KiB
4Időlimit túllépés2.085s34100 KiB
5Időlimit túllépés2.085s35632 KiB
6Időlimit túllépés2.085s46388 KiB
7Időlimit túllépés2.082s42116 KiB
8Elfogadva393ms43820 KiB
subtask313/13
9Elfogadva3ms1016 KiB
10Elfogadva3ms1004 KiB
11Elfogadva3ms1012 KiB
12Elfogadva3ms820 KiB
13Elfogadva3ms856 KiB
14Elfogadva3ms820 KiB
15Elfogadva4ms820 KiB
16Elfogadva3ms820 KiB
17Elfogadva3ms956 KiB
subtask410/10
18Elfogadva3ms1016 KiB
19Elfogadva3ms1004 KiB
20Elfogadva3ms1012 KiB
21Elfogadva3ms820 KiB
22Elfogadva3ms856 KiB
23Elfogadva3ms820 KiB
24Elfogadva4ms820 KiB
25Elfogadva3ms820 KiB
26Elfogadva3ms956 KiB
27Elfogadva158ms30736 KiB
28Elfogadva157ms30772 KiB
29Elfogadva151ms30752 KiB
30Elfogadva157ms30908 KiB
31Elfogadva157ms30940 KiB
32Elfogadva158ms30872 KiB
33Elfogadva234ms34100 KiB
34Elfogadva234ms34004 KiB
35Elfogadva226ms31812 KiB
36Elfogadva180ms40912 KiB
subtask50/15
37Elfogadva3ms1016 KiB
38Elfogadva3ms1004 KiB
39Elfogadva3ms1012 KiB
40Elfogadva3ms820 KiB
41Elfogadva3ms856 KiB
42Elfogadva3ms820 KiB
43Elfogadva4ms820 KiB
44Elfogadva3ms820 KiB
45Elfogadva3ms956 KiB
46Időlimit túllépés2.082s4148 KiB
47Időlimit túllépés2.084s3892 KiB
48Időlimit túllépés2.082s3892 KiB
49Időlimit túllépés2.082s3892 KiB
50Időlimit túllépés2.076s4032 KiB
51Időlimit túllépés2.076s3892 KiB
52Időlimit túllépés2.078s3892 KiB
53Időlimit túllépés2.078s4028 KiB
54Időlimit túllépés2.086s3892 KiB
55Időlimit túllépés2.086s4068 KiB
56Időlimit túllépés2.088s4076 KiB
57Időlimit túllépés2.088s3892 KiB
subtask610/10
58Elfogadva384ms34612 KiB
59Elfogadva384ms34612 KiB
60Elfogadva374ms34612 KiB
61Elfogadva382ms34612 KiB
62Elfogadva381ms34608 KiB
63Elfogadva372ms34488 KiB
64Elfogadva524ms38436 KiB
65Elfogadva508ms37552 KiB
66Elfogadva488ms36148 KiB
67Elfogadva377ms39040 KiB
subtask711/11
68Elfogadva3ms1016 KiB
69Elfogadva3ms1004 KiB
70Elfogadva3ms1012 KiB
71Elfogadva3ms820 KiB
72Elfogadva3ms856 KiB
73Elfogadva3ms820 KiB
74Elfogadva4ms820 KiB
75Elfogadva3ms820 KiB
76Elfogadva3ms956 KiB
77Elfogadva158ms30736 KiB
78Elfogadva157ms30772 KiB
79Elfogadva151ms30752 KiB
80Elfogadva157ms30908 KiB
81Elfogadva157ms30940 KiB
82Elfogadva158ms30872 KiB
83Elfogadva234ms34100 KiB
84Elfogadva234ms34004 KiB
85Elfogadva226ms31812 KiB
86Elfogadva180ms40912 KiB
87Elfogadva384ms34612 KiB
88Elfogadva384ms34612 KiB
89Elfogadva374ms34612 KiB
90Elfogadva382ms34612 KiB
91Elfogadva381ms34608 KiB
92Elfogadva372ms34488 KiB
93Elfogadva524ms38436 KiB
94Elfogadva508ms37552 KiB
95Elfogadva488ms36148 KiB
96Elfogadva377ms39040 KiB
97Elfogadva612ms34536 KiB
98Elfogadva606ms34576 KiB
99Elfogadva606ms34568 KiB
100Elfogadva612ms34608 KiB
101Elfogadva612ms34612 KiB
102Elfogadva605ms34632 KiB
103Elfogadva867ms38192 KiB
104Elfogadva846ms36848 KiB
105Elfogadva818ms35892 KiB
106Elfogadva596ms41780 KiB
subtask80/21
107Elfogadva1ms508 KiB
108Időlimit túllépés2.086s34100 KiB
109Időlimit túllépés2.088s33964 KiB
110Időlimit túllépés2.088s34100 KiB
111Időlimit túllépés2.102s33844 KiB
112Időlimit túllépés2.088s34100 KiB
113Időlimit túllépés2.088s34224 KiB
114Időlimit túllépés2.089s34016 KiB
115Elfogadva377ms34612 KiB
116Elfogadva386ms34612 KiB
117Elfogadva384ms34484 KiB
118Elfogadva384ms34612 KiB
119Elfogadva377ms34612 KiB
120Elfogadva377ms34612 KiB
121Időlimit túllépés2.086s33844 KiB
122Időlimit túllépés2.088s33848 KiB
subtask90/15
123Elfogadva1ms508 KiB
124Időlimit túllépés2.086s34100 KiB
125Időlimit túllépés2.085s46476 KiB
126Időlimit túllépés2.085s34100 KiB
127Időlimit túllépés2.085s35632 KiB
128Időlimit túllépés2.085s46388 KiB
129Időlimit túllépés2.082s42116 KiB
130Elfogadva393ms43820 KiB
131Elfogadva3ms1016 KiB
132Elfogadva3ms1004 KiB
133Elfogadva3ms1012 KiB
134Elfogadva3ms820 KiB
135Elfogadva3ms856 KiB
136Elfogadva3ms820 KiB
137Elfogadva4ms820 KiB
138Elfogadva3ms820 KiB
139Elfogadva3ms956 KiB
140Elfogadva158ms30736 KiB
141Elfogadva157ms30772 KiB
142Elfogadva151ms30752 KiB
143Elfogadva157ms30908 KiB
144Elfogadva157ms30940 KiB
145Elfogadva158ms30872 KiB
146Elfogadva234ms34100 KiB
147Elfogadva234ms34004 KiB
148Elfogadva226ms31812 KiB
149Elfogadva180ms40912 KiB
150Időlimit túllépés2.082s4148 KiB
151Időlimit túllépés2.084s3892 KiB
152Időlimit túllépés2.082s3892 KiB
153Időlimit túllépés2.082s3892 KiB
154Időlimit túllépés2.076s4032 KiB
155Időlimit túllépés2.076s3892 KiB
156Időlimit túllépés2.078s3892 KiB
157Időlimit túllépés2.078s4028 KiB
158Időlimit túllépés2.086s3892 KiB
159Időlimit túllépés2.086s4068 KiB
160Időlimit túllépés2.088s4076 KiB
161Időlimit túllépés2.088s3892 KiB
162Elfogadva384ms34612 KiB
163Elfogadva384ms34612 KiB
164Elfogadva374ms34612 KiB
165Elfogadva382ms34612 KiB
166Elfogadva381ms34608 KiB
167Elfogadva372ms34488 KiB
168Elfogadva524ms38436 KiB
169Elfogadva508ms37552 KiB
170Elfogadva488ms36148 KiB
171Elfogadva377ms39040 KiB
172Elfogadva612ms34536 KiB
173Elfogadva606ms34576 KiB
174Elfogadva606ms34568 KiB
175Elfogadva612ms34608 KiB
176Elfogadva612ms34612 KiB
177Elfogadva605ms34632 KiB
178Elfogadva867ms38192 KiB
179Elfogadva846ms36848 KiB
180Elfogadva818ms35892 KiB
181Elfogadva596ms41780 KiB
182Időlimit túllépés2.088s33964 KiB
183Időlimit túllépés2.088s34100 KiB
184Időlimit túllépés2.102s33844 KiB
185Időlimit túllépés2.088s34100 KiB
186Időlimit túllépés2.088s34224 KiB
187Időlimit túllépés2.089s34016 KiB
188Elfogadva377ms34612 KiB
189Elfogadva386ms34612 KiB
190Elfogadva384ms34484 KiB
191Elfogadva384ms34612 KiB
192Elfogadva377ms34612 KiB
193Elfogadva377ms34612 KiB
194Időlimit túllépés2.086s33844 KiB
195Időlimit túllépés2.088s33848 KiB
196Időlimit túllépés2.078s37172 KiB
197Időlimit túllépés2.078s37172 KiB
198Időlimit túllépés2.078s36656 KiB
199Időlimit túllépés2.078s35124 KiB
200Időlimit túllépés2.095s35124 KiB
201Időlimit túllépés2.095s34788 KiB
202Időlimit túllépés2.096s34388 KiB
203Időlimit túllépés2.095s34108 KiB
204Időlimit túllépés2.082s34016 KiB
205Időlimit túllépés2.085s34136 KiB