167312025-05-11 21:55:28szilSiklóernyőzéscpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Time limit exceeded2.088s34100 KiB
subtask20/5
3Time limit exceeded2.085s46476 KiB
4Time limit exceeded2.085s34100 KiB
5Time limit exceeded2.085s35632 KiB
6Time limit exceeded2.085s46388 KiB
7Time limit exceeded2.082s42116 KiB
8Accepted393ms43820 KiB
subtask313/13
9Accepted3ms1016 KiB
10Accepted3ms1004 KiB
11Accepted3ms1012 KiB
12Accepted3ms820 KiB
13Accepted3ms856 KiB
14Accepted3ms820 KiB
15Accepted4ms820 KiB
16Accepted3ms820 KiB
17Accepted3ms956 KiB
subtask410/10
18Accepted3ms1016 KiB
19Accepted3ms1004 KiB
20Accepted3ms1012 KiB
21Accepted3ms820 KiB
22Accepted3ms856 KiB
23Accepted3ms820 KiB
24Accepted4ms820 KiB
25Accepted3ms820 KiB
26Accepted3ms956 KiB
27Accepted158ms30736 KiB
28Accepted157ms30772 KiB
29Accepted151ms30752 KiB
30Accepted157ms30908 KiB
31Accepted157ms30940 KiB
32Accepted158ms30872 KiB
33Accepted234ms34100 KiB
34Accepted234ms34004 KiB
35Accepted226ms31812 KiB
36Accepted180ms40912 KiB
subtask50/15
37Accepted3ms1016 KiB
38Accepted3ms1004 KiB
39Accepted3ms1012 KiB
40Accepted3ms820 KiB
41Accepted3ms856 KiB
42Accepted3ms820 KiB
43Accepted4ms820 KiB
44Accepted3ms820 KiB
45Accepted3ms956 KiB
46Time limit exceeded2.082s4148 KiB
47Time limit exceeded2.084s3892 KiB
48Time limit exceeded2.082s3892 KiB
49Time limit exceeded2.082s3892 KiB
50Time limit exceeded2.076s4032 KiB
51Time limit exceeded2.076s3892 KiB
52Time limit exceeded2.078s3892 KiB
53Time limit exceeded2.078s4028 KiB
54Time limit exceeded2.086s3892 KiB
55Time limit exceeded2.086s4068 KiB
56Time limit exceeded2.088s4076 KiB
57Time limit exceeded2.088s3892 KiB
subtask610/10
58Accepted384ms34612 KiB
59Accepted384ms34612 KiB
60Accepted374ms34612 KiB
61Accepted382ms34612 KiB
62Accepted381ms34608 KiB
63Accepted372ms34488 KiB
64Accepted524ms38436 KiB
65Accepted508ms37552 KiB
66Accepted488ms36148 KiB
67Accepted377ms39040 KiB
subtask711/11
68Accepted3ms1016 KiB
69Accepted3ms1004 KiB
70Accepted3ms1012 KiB
71Accepted3ms820 KiB
72Accepted3ms856 KiB
73Accepted3ms820 KiB
74Accepted4ms820 KiB
75Accepted3ms820 KiB
76Accepted3ms956 KiB
77Accepted158ms30736 KiB
78Accepted157ms30772 KiB
79Accepted151ms30752 KiB
80Accepted157ms30908 KiB
81Accepted157ms30940 KiB
82Accepted158ms30872 KiB
83Accepted234ms34100 KiB
84Accepted234ms34004 KiB
85Accepted226ms31812 KiB
86Accepted180ms40912 KiB
87Accepted384ms34612 KiB
88Accepted384ms34612 KiB
89Accepted374ms34612 KiB
90Accepted382ms34612 KiB
91Accepted381ms34608 KiB
92Accepted372ms34488 KiB
93Accepted524ms38436 KiB
94Accepted508ms37552 KiB
95Accepted488ms36148 KiB
96Accepted377ms39040 KiB
97Accepted612ms34536 KiB
98Accepted606ms34576 KiB
99Accepted606ms34568 KiB
100Accepted612ms34608 KiB
101Accepted612ms34612 KiB
102Accepted605ms34632 KiB
103Accepted867ms38192 KiB
104Accepted846ms36848 KiB
105Accepted818ms35892 KiB
106Accepted596ms41780 KiB
subtask80/21
107Accepted1ms508 KiB
108Time limit exceeded2.086s34100 KiB
109Time limit exceeded2.088s33964 KiB
110Time limit exceeded2.088s34100 KiB
111Time limit exceeded2.102s33844 KiB
112Time limit exceeded2.088s34100 KiB
113Time limit exceeded2.088s34224 KiB
114Time limit exceeded2.089s34016 KiB
115Accepted377ms34612 KiB
116Accepted386ms34612 KiB
117Accepted384ms34484 KiB
118Accepted384ms34612 KiB
119Accepted377ms34612 KiB
120Accepted377ms34612 KiB
121Time limit exceeded2.086s33844 KiB
122Time limit exceeded2.088s33848 KiB
subtask90/15
123Accepted1ms508 KiB
124Time limit exceeded2.086s34100 KiB
125Time limit exceeded2.085s46476 KiB
126Time limit exceeded2.085s34100 KiB
127Time limit exceeded2.085s35632 KiB
128Time limit exceeded2.085s46388 KiB
129Time limit exceeded2.082s42116 KiB
130Accepted393ms43820 KiB
131Accepted3ms1016 KiB
132Accepted3ms1004 KiB
133Accepted3ms1012 KiB
134Accepted3ms820 KiB
135Accepted3ms856 KiB
136Accepted3ms820 KiB
137Accepted4ms820 KiB
138Accepted3ms820 KiB
139Accepted3ms956 KiB
140Accepted158ms30736 KiB
141Accepted157ms30772 KiB
142Accepted151ms30752 KiB
143Accepted157ms30908 KiB
144Accepted157ms30940 KiB
145Accepted158ms30872 KiB
146Accepted234ms34100 KiB
147Accepted234ms34004 KiB
148Accepted226ms31812 KiB
149Accepted180ms40912 KiB
150Time limit exceeded2.082s4148 KiB
151Time limit exceeded2.084s3892 KiB
152Time limit exceeded2.082s3892 KiB
153Time limit exceeded2.082s3892 KiB
154Time limit exceeded2.076s4032 KiB
155Time limit exceeded2.076s3892 KiB
156Time limit exceeded2.078s3892 KiB
157Time limit exceeded2.078s4028 KiB
158Time limit exceeded2.086s3892 KiB
159Time limit exceeded2.086s4068 KiB
160Time limit exceeded2.088s4076 KiB
161Time limit exceeded2.088s3892 KiB
162Accepted384ms34612 KiB
163Accepted384ms34612 KiB
164Accepted374ms34612 KiB
165Accepted382ms34612 KiB
166Accepted381ms34608 KiB
167Accepted372ms34488 KiB
168Accepted524ms38436 KiB
169Accepted508ms37552 KiB
170Accepted488ms36148 KiB
171Accepted377ms39040 KiB
172Accepted612ms34536 KiB
173Accepted606ms34576 KiB
174Accepted606ms34568 KiB
175Accepted612ms34608 KiB
176Accepted612ms34612 KiB
177Accepted605ms34632 KiB
178Accepted867ms38192 KiB
179Accepted846ms36848 KiB
180Accepted818ms35892 KiB
181Accepted596ms41780 KiB
182Time limit exceeded2.088s33964 KiB
183Time limit exceeded2.088s34100 KiB
184Time limit exceeded2.102s33844 KiB
185Time limit exceeded2.088s34100 KiB
186Time limit exceeded2.088s34224 KiB
187Time limit exceeded2.089s34016 KiB
188Accepted377ms34612 KiB
189Accepted386ms34612 KiB
190Accepted384ms34484 KiB
191Accepted384ms34612 KiB
192Accepted377ms34612 KiB
193Accepted377ms34612 KiB
194Time limit exceeded2.086s33844 KiB
195Time limit exceeded2.088s33848 KiB
196Time limit exceeded2.078s37172 KiB
197Time limit exceeded2.078s37172 KiB
198Time limit exceeded2.078s36656 KiB
199Time limit exceeded2.078s35124 KiB
200Time limit exceeded2.095s35124 KiB
201Time limit exceeded2.095s34788 KiB
202Time limit exceeded2.096s34388 KiB
203Time limit exceeded2.095s34108 KiB
204Time limit exceeded2.082s34016 KiB
205Time limit exceeded2.085s34136 KiB