167332025-05-11 22:01:00szilSiklóernyőzéscpp17Időlimit túllépés 59/1002.101s46532 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];
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;
    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);
    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
1Elfogadva1ms508 KiB
2Időlimit túllépés2.082s33844 KiB
subtask20/5
3Időlimit túllépés2.094s46532 KiB
4Időlimit túllépés2.092s34104 KiB
5Időlimit túllépés2.094s35572 KiB
6Időlimit túllépés2.094s46388 KiB
7Időlimit túllépés2.082s42088 KiB
8Elfogadva391ms43828 KiB
subtask313/13
9Elfogadva3ms820 KiB
10Elfogadva3ms1004 KiB
11Elfogadva3ms820 KiB
12Elfogadva3ms820 KiB
13Elfogadva3ms820 KiB
14Elfogadva3ms820 KiB
15Elfogadva3ms820 KiB
16Elfogadva3ms820 KiB
17Elfogadva3ms820 KiB
subtask410/10
18Elfogadva3ms820 KiB
19Elfogadva3ms1004 KiB
20Elfogadva3ms820 KiB
21Elfogadva3ms820 KiB
22Elfogadva3ms820 KiB
23Elfogadva3ms820 KiB
24Elfogadva3ms820 KiB
25Elfogadva3ms820 KiB
26Elfogadva3ms820 KiB
27Elfogadva158ms30776 KiB
28Elfogadva150ms30916 KiB
29Elfogadva156ms30720 KiB
30Elfogadva150ms30912 KiB
31Elfogadva157ms30948 KiB
32Elfogadva157ms30920 KiB
33Elfogadva234ms33844 KiB
34Elfogadva233ms33908 KiB
35Elfogadva225ms31796 KiB
36Elfogadva180ms41012 KiB
subtask515/15
37Elfogadva3ms820 KiB
38Elfogadva3ms1004 KiB
39Elfogadva3ms820 KiB
40Elfogadva3ms820 KiB
41Elfogadva3ms820 KiB
42Elfogadva3ms820 KiB
43Elfogadva3ms820 KiB
44Elfogadva3ms820 KiB
45Elfogadva3ms820 KiB
46Elfogadva959ms4916 KiB
47Elfogadva1.047s4808 KiB
48Elfogadva709ms4660 KiB
49Elfogadva703ms4888 KiB
50Elfogadva1.103s4548 KiB
51Elfogadva1.095s4404 KiB
52Elfogadva1.103s4540 KiB
53Elfogadva1.095s4408 KiB
54Elfogadva1.687s4848 KiB
55Elfogadva1.61s4836 KiB
56Elfogadva1.554s4840 KiB
57Elfogadva1.46s4656 KiB
subtask610/10
58Elfogadva388ms34612 KiB
59Elfogadva382ms34612 KiB
60Elfogadva388ms34700 KiB
61Elfogadva381ms34620 KiB
62Elfogadva389ms34608 KiB
63Elfogadva379ms34612 KiB
64Elfogadva532ms38520 KiB
65Elfogadva515ms37676 KiB
66Elfogadva501ms36148 KiB
67Elfogadva386ms39196 KiB
subtask711/11
68Elfogadva3ms820 KiB
69Elfogadva3ms1004 KiB
70Elfogadva3ms820 KiB
71Elfogadva3ms820 KiB
72Elfogadva3ms820 KiB
73Elfogadva3ms820 KiB
74Elfogadva3ms820 KiB
75Elfogadva3ms820 KiB
76Elfogadva3ms820 KiB
77Elfogadva158ms30776 KiB
78Elfogadva150ms30916 KiB
79Elfogadva156ms30720 KiB
80Elfogadva150ms30912 KiB
81Elfogadva157ms30948 KiB
82Elfogadva157ms30920 KiB
83Elfogadva234ms33844 KiB
84Elfogadva233ms33908 KiB
85Elfogadva225ms31796 KiB
86Elfogadva180ms41012 KiB
87Elfogadva388ms34612 KiB
88Elfogadva382ms34612 KiB
89Elfogadva388ms34700 KiB
90Elfogadva381ms34620 KiB
91Elfogadva389ms34608 KiB
92Elfogadva379ms34612 KiB
93Elfogadva532ms38520 KiB
94Elfogadva515ms37676 KiB
95Elfogadva501ms36148 KiB
96Elfogadva386ms39196 KiB
97Elfogadva624ms34488 KiB
98Elfogadva620ms34608 KiB
99Elfogadva625ms34612 KiB
100Elfogadva628ms34616 KiB
101Elfogadva630ms34612 KiB
102Elfogadva628ms34616 KiB
103Elfogadva883ms38336 KiB
104Elfogadva853ms36832 KiB
105Elfogadva832ms35896 KiB
106Elfogadva619ms41780 KiB
subtask80/21
107Elfogadva1ms316 KiB
108Időlimit túllépés2.086s34056 KiB
109Időlimit túllépés2.086s34036 KiB
110Időlimit túllépés2.086s34108 KiB
111Időlimit túllépés2.101s34056 KiB
112Időlimit túllépés2.091s33904 KiB
113Időlimit túllépés2.092s33856 KiB
114Időlimit túllépés2.092s34096 KiB
115Elfogadva386ms34552 KiB
116Elfogadva386ms34612 KiB
117Elfogadva386ms34608 KiB
118Elfogadva386ms34456 KiB
119Elfogadva395ms34596 KiB
120Elfogadva395ms34636 KiB
121Időlimit túllépés2.092s34020 KiB
122Időlimit túllépés2.088s34100 KiB
subtask90/15
123Elfogadva1ms316 KiB
124Időlimit túllépés2.086s34056 KiB
125Időlimit túllépés2.094s46532 KiB
126Időlimit túllépés2.092s34104 KiB
127Időlimit túllépés2.094s35572 KiB
128Időlimit túllépés2.094s46388 KiB
129Időlimit túllépés2.082s42088 KiB
130Elfogadva391ms43828 KiB
131Elfogadva3ms820 KiB
132Elfogadva3ms1004 KiB
133Elfogadva3ms820 KiB
134Elfogadva3ms820 KiB
135Elfogadva3ms820 KiB
136Elfogadva3ms820 KiB
137Elfogadva3ms820 KiB
138Elfogadva3ms820 KiB
139Elfogadva3ms820 KiB
140Elfogadva158ms30776 KiB
141Elfogadva150ms30916 KiB
142Elfogadva156ms30720 KiB
143Elfogadva150ms30912 KiB
144Elfogadva157ms30948 KiB
145Elfogadva157ms30920 KiB
146Elfogadva234ms33844 KiB
147Elfogadva233ms33908 KiB
148Elfogadva225ms31796 KiB
149Elfogadva180ms41012 KiB
150Elfogadva959ms4916 KiB
151Elfogadva1.047s4808 KiB
152Elfogadva709ms4660 KiB
153Elfogadva703ms4888 KiB
154Elfogadva1.103s4548 KiB
155Elfogadva1.095s4404 KiB
156Elfogadva1.103s4540 KiB
157Elfogadva1.095s4408 KiB
158Elfogadva1.687s4848 KiB
159Elfogadva1.61s4836 KiB
160Elfogadva1.554s4840 KiB
161Elfogadva1.46s4656 KiB
162Elfogadva388ms34612 KiB
163Elfogadva382ms34612 KiB
164Elfogadva388ms34700 KiB
165Elfogadva381ms34620 KiB
166Elfogadva389ms34608 KiB
167Elfogadva379ms34612 KiB
168Elfogadva532ms38520 KiB
169Elfogadva515ms37676 KiB
170Elfogadva501ms36148 KiB
171Elfogadva386ms39196 KiB
172Elfogadva624ms34488 KiB
173Elfogadva620ms34608 KiB
174Elfogadva625ms34612 KiB
175Elfogadva628ms34616 KiB
176Elfogadva630ms34612 KiB
177Elfogadva628ms34616 KiB
178Elfogadva883ms38336 KiB
179Elfogadva853ms36832 KiB
180Elfogadva832ms35896 KiB
181Elfogadva619ms41780 KiB
182Időlimit túllépés2.086s34036 KiB
183Időlimit túllépés2.086s34108 KiB
184Időlimit túllépés2.101s34056 KiB
185Időlimit túllépés2.091s33904 KiB
186Időlimit túllépés2.092s33856 KiB
187Időlimit túllépés2.092s34096 KiB
188Elfogadva386ms34552 KiB
189Elfogadva386ms34612 KiB
190Elfogadva386ms34608 KiB
191Elfogadva386ms34456 KiB
192Elfogadva395ms34596 KiB
193Elfogadva395ms34636 KiB
194Időlimit túllépés2.092s34020 KiB
195Időlimit túllépés2.088s34100 KiB
196Időlimit túllépés2.085s37220 KiB
197Időlimit túllépés2.085s37088 KiB
198Időlimit túllépés2.085s36896 KiB
199Időlimit túllépés2.085s35124 KiB
200Időlimit túllépés2.084s35124 KiB
201Időlimit túllépés2.085s34872 KiB
202Időlimit túllépés2.085s34508 KiB
203Időlimit túllépés2.085s34284 KiB
204Időlimit túllépés2.091s34188 KiB
205Időlimit túllépés2.092s34100 KiB