167322025-05-11 21:58:34szilSiklóernyőzéscpp17Időlimit túllépés 23/1002.102s34020 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

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(8*n);
    }

    void push(int v) {
        if (v > 4*n) return;

        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.091s21740 KiB
subtask20/5
3Időlimit túllépés2.092s34020 KiB
4Időlimit túllépés2.091s21436 KiB
5Időlimit túllépés2.091s23136 KiB
6Időlimit túllépés2.092s33832 KiB
7Időlimit túllépés2.078s29492 KiB
8Elfogadva358ms31344 KiB
subtask313/13
9Elfogadva3ms564 KiB
10Elfogadva3ms756 KiB
11Elfogadva3ms564 KiB
12Elfogadva3ms564 KiB
13Elfogadva3ms564 KiB
14Elfogadva3ms564 KiB
15Elfogadva3ms564 KiB
16Elfogadva3ms564 KiB
17Elfogadva3ms820 KiB
subtask410/10
18Elfogadva3ms564 KiB
19Elfogadva3ms756 KiB
20Elfogadva3ms564 KiB
21Elfogadva3ms564 KiB
22Elfogadva3ms564 KiB
23Elfogadva3ms564 KiB
24Elfogadva3ms564 KiB
25Elfogadva3ms564 KiB
26Elfogadva3ms820 KiB
27Elfogadva133ms18424 KiB
28Elfogadva136ms18308 KiB
29Elfogadva136ms18240 KiB
30Elfogadva133ms18240 KiB
31Elfogadva133ms18228 KiB
32Elfogadva136ms18432 KiB
33Elfogadva201ms21556 KiB
34Elfogadva203ms21432 KiB
35Elfogadva192ms19392 KiB
36Elfogadva152ms28412 KiB
subtask50/15
37Elfogadva3ms564 KiB
38Elfogadva3ms756 KiB
39Elfogadva3ms564 KiB
40Elfogadva3ms564 KiB
41Elfogadva3ms564 KiB
42Elfogadva3ms564 KiB
43Elfogadva3ms564 KiB
44Elfogadva3ms564 KiB
45Elfogadva3ms820 KiB
46Időlimit túllépés2.076s3892 KiB
47Időlimit túllépés2.075s3632 KiB
48Időlimit túllépés2.075s3900 KiB
49Időlimit túllépés2.075s3924 KiB
50Időlimit túllépés2.078s3856 KiB
51Időlimit túllépés2.078s3844 KiB
52Időlimit túllépés2.079s3636 KiB
53Időlimit túllépés2.079s3728 KiB
54Időlimit túllépés2.088s3636 KiB
55Időlimit túllépés2.088s3644 KiB
56Időlimit túllépés2.089s3636 KiB
57Időlimit túllépés2.089s3832 KiB
subtask60/10
58Elfogadva358ms22060 KiB
59Elfogadva358ms21948 KiB
60Elfogadva351ms22100 KiB
61Elfogadva352ms22092 KiB
62Elfogadva358ms22068 KiB
63Elfogadva358ms22004 KiB
64Elfogadva467ms25996 KiB
65Elfogadva458ms25144 KiB
66Elfogadva448ms23604 KiB
67Hibás válasz351ms26624 KiB
subtask70/11
68Elfogadva3ms564 KiB
69Elfogadva3ms756 KiB
70Elfogadva3ms564 KiB
71Elfogadva3ms564 KiB
72Elfogadva3ms564 KiB
73Elfogadva3ms564 KiB
74Elfogadva3ms564 KiB
75Elfogadva3ms564 KiB
76Elfogadva3ms820 KiB
77Elfogadva133ms18424 KiB
78Elfogadva136ms18308 KiB
79Elfogadva136ms18240 KiB
80Elfogadva133ms18240 KiB
81Elfogadva133ms18228 KiB
82Elfogadva136ms18432 KiB
83Elfogadva201ms21556 KiB
84Elfogadva203ms21432 KiB
85Elfogadva192ms19392 KiB
86Elfogadva152ms28412 KiB
87Elfogadva358ms22060 KiB
88Elfogadva358ms21948 KiB
89Elfogadva351ms22100 KiB
90Elfogadva352ms22092 KiB
91Elfogadva358ms22068 KiB
92Elfogadva358ms22004 KiB
93Elfogadva467ms25996 KiB
94Elfogadva458ms25144 KiB
95Elfogadva448ms23604 KiB
96Hibás válasz351ms26624 KiB
97Elfogadva578ms22064 KiB
98Hibás válasz582ms22064 KiB
99Elfogadva580ms22076 KiB
100Elfogadva574ms22104 KiB
101Elfogadva582ms22068 KiB
102Elfogadva574ms22064 KiB
103Hibás válasz787ms25900 KiB
104Elfogadva762ms24212 KiB
105Hibás válasz740ms23396 KiB
106Hibás válasz559ms29236 KiB
subtask80/21
107Elfogadva1ms508 KiB
108Időlimit túllépés2.081s21552 KiB
109Időlimit túllépés2.081s21556 KiB
110Időlimit túllépés2.081s21556 KiB
111Időlimit túllépés2.102s21556 KiB
112Időlimit túllépés2.085s21564 KiB
113Időlimit túllépés2.085s21488 KiB
114Időlimit túllépés2.085s21556 KiB
115Elfogadva363ms21948 KiB
116Elfogadva363ms22080 KiB
117Elfogadva354ms22068 KiB
118Elfogadva358ms22072 KiB
119Elfogadva356ms22068 KiB
120Elfogadva361ms22004 KiB
121Időlimit túllépés2.095s21556 KiB
122Időlimit túllépés2.088s21556 KiB
subtask90/15
123Elfogadva1ms508 KiB
124Időlimit túllépés2.081s21552 KiB
125Időlimit túllépés2.092s34020 KiB
126Időlimit túllépés2.091s21436 KiB
127Időlimit túllépés2.091s23136 KiB
128Időlimit túllépés2.092s33832 KiB
129Időlimit túllépés2.078s29492 KiB
130Elfogadva358ms31344 KiB
131Elfogadva3ms564 KiB
132Elfogadva3ms756 KiB
133Elfogadva3ms564 KiB
134Elfogadva3ms564 KiB
135Elfogadva3ms564 KiB
136Elfogadva3ms564 KiB
137Elfogadva3ms564 KiB
138Elfogadva3ms564 KiB
139Elfogadva3ms820 KiB
140Elfogadva133ms18424 KiB
141Elfogadva136ms18308 KiB
142Elfogadva136ms18240 KiB
143Elfogadva133ms18240 KiB
144Elfogadva133ms18228 KiB
145Elfogadva136ms18432 KiB
146Elfogadva201ms21556 KiB
147Elfogadva203ms21432 KiB
148Elfogadva192ms19392 KiB
149Elfogadva152ms28412 KiB
150Időlimit túllépés2.076s3892 KiB
151Időlimit túllépés2.075s3632 KiB
152Időlimit túllépés2.075s3900 KiB
153Időlimit túllépés2.075s3924 KiB
154Időlimit túllépés2.078s3856 KiB
155Időlimit túllépés2.078s3844 KiB
156Időlimit túllépés2.079s3636 KiB
157Időlimit túllépés2.079s3728 KiB
158Időlimit túllépés2.088s3636 KiB
159Időlimit túllépés2.088s3644 KiB
160Időlimit túllépés2.089s3636 KiB
161Időlimit túllépés2.089s3832 KiB
162Elfogadva358ms22060 KiB
163Elfogadva358ms21948 KiB
164Elfogadva351ms22100 KiB
165Elfogadva352ms22092 KiB
166Elfogadva358ms22068 KiB
167Elfogadva358ms22004 KiB
168Elfogadva467ms25996 KiB
169Elfogadva458ms25144 KiB
170Elfogadva448ms23604 KiB
171Hibás válasz351ms26624 KiB
172Elfogadva578ms22064 KiB
173Hibás válasz582ms22064 KiB
174Elfogadva580ms22076 KiB
175Elfogadva574ms22104 KiB
176Elfogadva582ms22068 KiB
177Elfogadva574ms22064 KiB
178Hibás válasz787ms25900 KiB
179Elfogadva762ms24212 KiB
180Hibás válasz740ms23396 KiB
181Hibás válasz559ms29236 KiB
182Időlimit túllépés2.081s21556 KiB
183Időlimit túllépés2.081s21556 KiB
184Időlimit túllépés2.102s21556 KiB
185Időlimit túllépés2.085s21564 KiB
186Időlimit túllépés2.085s21488 KiB
187Időlimit túllépés2.085s21556 KiB
188Elfogadva363ms21948 KiB
189Elfogadva363ms22080 KiB
190Elfogadva354ms22068 KiB
191Elfogadva358ms22072 KiB
192Elfogadva356ms22068 KiB
193Elfogadva361ms22004 KiB
194Időlimit túllépés2.095s21556 KiB
195Időlimit túllépés2.088s21556 KiB
196Időlimit túllépés2.086s24660 KiB
197Időlimit túllépés2.086s24632 KiB
198Időlimit túllépés2.086s24116 KiB
199Időlimit túllépés2.085s22792 KiB
200Időlimit túllépés2.092s22796 KiB
201Időlimit túllépés2.094s22324 KiB
202Időlimit túllépés2.092s21824 KiB
203Időlimit túllépés2.094s21552 KiB
204Időlimit túllépés2.091s21556 KiB
205Időlimit túllépés2.092s21556 KiB