167322025-05-11 21:58:34szilSiklóernyőzéscpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Time limit exceeded2.091s21740 KiB
subtask20/5
3Time limit exceeded2.092s34020 KiB
4Time limit exceeded2.091s21436 KiB
5Time limit exceeded2.091s23136 KiB
6Time limit exceeded2.092s33832 KiB
7Time limit exceeded2.078s29492 KiB
8Accepted358ms31344 KiB
subtask313/13
9Accepted3ms564 KiB
10Accepted3ms756 KiB
11Accepted3ms564 KiB
12Accepted3ms564 KiB
13Accepted3ms564 KiB
14Accepted3ms564 KiB
15Accepted3ms564 KiB
16Accepted3ms564 KiB
17Accepted3ms820 KiB
subtask410/10
18Accepted3ms564 KiB
19Accepted3ms756 KiB
20Accepted3ms564 KiB
21Accepted3ms564 KiB
22Accepted3ms564 KiB
23Accepted3ms564 KiB
24Accepted3ms564 KiB
25Accepted3ms564 KiB
26Accepted3ms820 KiB
27Accepted133ms18424 KiB
28Accepted136ms18308 KiB
29Accepted136ms18240 KiB
30Accepted133ms18240 KiB
31Accepted133ms18228 KiB
32Accepted136ms18432 KiB
33Accepted201ms21556 KiB
34Accepted203ms21432 KiB
35Accepted192ms19392 KiB
36Accepted152ms28412 KiB
subtask50/15
37Accepted3ms564 KiB
38Accepted3ms756 KiB
39Accepted3ms564 KiB
40Accepted3ms564 KiB
41Accepted3ms564 KiB
42Accepted3ms564 KiB
43Accepted3ms564 KiB
44Accepted3ms564 KiB
45Accepted3ms820 KiB
46Time limit exceeded2.076s3892 KiB
47Time limit exceeded2.075s3632 KiB
48Time limit exceeded2.075s3900 KiB
49Time limit exceeded2.075s3924 KiB
50Time limit exceeded2.078s3856 KiB
51Time limit exceeded2.078s3844 KiB
52Time limit exceeded2.079s3636 KiB
53Time limit exceeded2.079s3728 KiB
54Time limit exceeded2.088s3636 KiB
55Time limit exceeded2.088s3644 KiB
56Time limit exceeded2.089s3636 KiB
57Time limit exceeded2.089s3832 KiB
subtask60/10
58Accepted358ms22060 KiB
59Accepted358ms21948 KiB
60Accepted351ms22100 KiB
61Accepted352ms22092 KiB
62Accepted358ms22068 KiB
63Accepted358ms22004 KiB
64Accepted467ms25996 KiB
65Accepted458ms25144 KiB
66Accepted448ms23604 KiB
67Wrong answer351ms26624 KiB
subtask70/11
68Accepted3ms564 KiB
69Accepted3ms756 KiB
70Accepted3ms564 KiB
71Accepted3ms564 KiB
72Accepted3ms564 KiB
73Accepted3ms564 KiB
74Accepted3ms564 KiB
75Accepted3ms564 KiB
76Accepted3ms820 KiB
77Accepted133ms18424 KiB
78Accepted136ms18308 KiB
79Accepted136ms18240 KiB
80Accepted133ms18240 KiB
81Accepted133ms18228 KiB
82Accepted136ms18432 KiB
83Accepted201ms21556 KiB
84Accepted203ms21432 KiB
85Accepted192ms19392 KiB
86Accepted152ms28412 KiB
87Accepted358ms22060 KiB
88Accepted358ms21948 KiB
89Accepted351ms22100 KiB
90Accepted352ms22092 KiB
91Accepted358ms22068 KiB
92Accepted358ms22004 KiB
93Accepted467ms25996 KiB
94Accepted458ms25144 KiB
95Accepted448ms23604 KiB
96Wrong answer351ms26624 KiB
97Accepted578ms22064 KiB
98Wrong answer582ms22064 KiB
99Accepted580ms22076 KiB
100Accepted574ms22104 KiB
101Accepted582ms22068 KiB
102Accepted574ms22064 KiB
103Wrong answer787ms25900 KiB
104Accepted762ms24212 KiB
105Wrong answer740ms23396 KiB
106Wrong answer559ms29236 KiB
subtask80/21
107Accepted1ms508 KiB
108Time limit exceeded2.081s21552 KiB
109Time limit exceeded2.081s21556 KiB
110Time limit exceeded2.081s21556 KiB
111Time limit exceeded2.102s21556 KiB
112Time limit exceeded2.085s21564 KiB
113Time limit exceeded2.085s21488 KiB
114Time limit exceeded2.085s21556 KiB
115Accepted363ms21948 KiB
116Accepted363ms22080 KiB
117Accepted354ms22068 KiB
118Accepted358ms22072 KiB
119Accepted356ms22068 KiB
120Accepted361ms22004 KiB
121Time limit exceeded2.095s21556 KiB
122Time limit exceeded2.088s21556 KiB
subtask90/15
123Accepted1ms508 KiB
124Time limit exceeded2.081s21552 KiB
125Time limit exceeded2.092s34020 KiB
126Time limit exceeded2.091s21436 KiB
127Time limit exceeded2.091s23136 KiB
128Time limit exceeded2.092s33832 KiB
129Time limit exceeded2.078s29492 KiB
130Accepted358ms31344 KiB
131Accepted3ms564 KiB
132Accepted3ms756 KiB
133Accepted3ms564 KiB
134Accepted3ms564 KiB
135Accepted3ms564 KiB
136Accepted3ms564 KiB
137Accepted3ms564 KiB
138Accepted3ms564 KiB
139Accepted3ms820 KiB
140Accepted133ms18424 KiB
141Accepted136ms18308 KiB
142Accepted136ms18240 KiB
143Accepted133ms18240 KiB
144Accepted133ms18228 KiB
145Accepted136ms18432 KiB
146Accepted201ms21556 KiB
147Accepted203ms21432 KiB
148Accepted192ms19392 KiB
149Accepted152ms28412 KiB
150Time limit exceeded2.076s3892 KiB
151Time limit exceeded2.075s3632 KiB
152Time limit exceeded2.075s3900 KiB
153Time limit exceeded2.075s3924 KiB
154Time limit exceeded2.078s3856 KiB
155Time limit exceeded2.078s3844 KiB
156Time limit exceeded2.079s3636 KiB
157Time limit exceeded2.079s3728 KiB
158Time limit exceeded2.088s3636 KiB
159Time limit exceeded2.088s3644 KiB
160Time limit exceeded2.089s3636 KiB
161Time limit exceeded2.089s3832 KiB
162Accepted358ms22060 KiB
163Accepted358ms21948 KiB
164Accepted351ms22100 KiB
165Accepted352ms22092 KiB
166Accepted358ms22068 KiB
167Accepted358ms22004 KiB
168Accepted467ms25996 KiB
169Accepted458ms25144 KiB
170Accepted448ms23604 KiB
171Wrong answer351ms26624 KiB
172Accepted578ms22064 KiB
173Wrong answer582ms22064 KiB
174Accepted580ms22076 KiB
175Accepted574ms22104 KiB
176Accepted582ms22068 KiB
177Accepted574ms22064 KiB
178Wrong answer787ms25900 KiB
179Accepted762ms24212 KiB
180Wrong answer740ms23396 KiB
181Wrong answer559ms29236 KiB
182Time limit exceeded2.081s21556 KiB
183Time limit exceeded2.081s21556 KiB
184Time limit exceeded2.102s21556 KiB
185Time limit exceeded2.085s21564 KiB
186Time limit exceeded2.085s21488 KiB
187Time limit exceeded2.085s21556 KiB
188Accepted363ms21948 KiB
189Accepted363ms22080 KiB
190Accepted354ms22068 KiB
191Accepted358ms22072 KiB
192Accepted356ms22068 KiB
193Accepted361ms22004 KiB
194Time limit exceeded2.095s21556 KiB
195Time limit exceeded2.088s21556 KiB
196Time limit exceeded2.086s24660 KiB
197Time limit exceeded2.086s24632 KiB
198Time limit exceeded2.086s24116 KiB
199Time limit exceeded2.085s22792 KiB
200Time limit exceeded2.092s22796 KiB
201Time limit exceeded2.094s22324 KiB
202Time limit exceeded2.092s21824 KiB
203Time limit exceeded2.094s21552 KiB
204Time limit exceeded2.091s21556 KiB
205Time limit exceeded2.092s21556 KiB