167332025-05-11 22:01:00szilSiklóernyőzéscpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms508 KiB
2Time limit exceeded2.082s33844 KiB
subtask20/5
3Time limit exceeded2.094s46532 KiB
4Time limit exceeded2.092s34104 KiB
5Time limit exceeded2.094s35572 KiB
6Time limit exceeded2.094s46388 KiB
7Time limit exceeded2.082s42088 KiB
8Accepted391ms43828 KiB
subtask313/13
9Accepted3ms820 KiB
10Accepted3ms1004 KiB
11Accepted3ms820 KiB
12Accepted3ms820 KiB
13Accepted3ms820 KiB
14Accepted3ms820 KiB
15Accepted3ms820 KiB
16Accepted3ms820 KiB
17Accepted3ms820 KiB
subtask410/10
18Accepted3ms820 KiB
19Accepted3ms1004 KiB
20Accepted3ms820 KiB
21Accepted3ms820 KiB
22Accepted3ms820 KiB
23Accepted3ms820 KiB
24Accepted3ms820 KiB
25Accepted3ms820 KiB
26Accepted3ms820 KiB
27Accepted158ms30776 KiB
28Accepted150ms30916 KiB
29Accepted156ms30720 KiB
30Accepted150ms30912 KiB
31Accepted157ms30948 KiB
32Accepted157ms30920 KiB
33Accepted234ms33844 KiB
34Accepted233ms33908 KiB
35Accepted225ms31796 KiB
36Accepted180ms41012 KiB
subtask515/15
37Accepted3ms820 KiB
38Accepted3ms1004 KiB
39Accepted3ms820 KiB
40Accepted3ms820 KiB
41Accepted3ms820 KiB
42Accepted3ms820 KiB
43Accepted3ms820 KiB
44Accepted3ms820 KiB
45Accepted3ms820 KiB
46Accepted959ms4916 KiB
47Accepted1.047s4808 KiB
48Accepted709ms4660 KiB
49Accepted703ms4888 KiB
50Accepted1.103s4548 KiB
51Accepted1.095s4404 KiB
52Accepted1.103s4540 KiB
53Accepted1.095s4408 KiB
54Accepted1.687s4848 KiB
55Accepted1.61s4836 KiB
56Accepted1.554s4840 KiB
57Accepted1.46s4656 KiB
subtask610/10
58Accepted388ms34612 KiB
59Accepted382ms34612 KiB
60Accepted388ms34700 KiB
61Accepted381ms34620 KiB
62Accepted389ms34608 KiB
63Accepted379ms34612 KiB
64Accepted532ms38520 KiB
65Accepted515ms37676 KiB
66Accepted501ms36148 KiB
67Accepted386ms39196 KiB
subtask711/11
68Accepted3ms820 KiB
69Accepted3ms1004 KiB
70Accepted3ms820 KiB
71Accepted3ms820 KiB
72Accepted3ms820 KiB
73Accepted3ms820 KiB
74Accepted3ms820 KiB
75Accepted3ms820 KiB
76Accepted3ms820 KiB
77Accepted158ms30776 KiB
78Accepted150ms30916 KiB
79Accepted156ms30720 KiB
80Accepted150ms30912 KiB
81Accepted157ms30948 KiB
82Accepted157ms30920 KiB
83Accepted234ms33844 KiB
84Accepted233ms33908 KiB
85Accepted225ms31796 KiB
86Accepted180ms41012 KiB
87Accepted388ms34612 KiB
88Accepted382ms34612 KiB
89Accepted388ms34700 KiB
90Accepted381ms34620 KiB
91Accepted389ms34608 KiB
92Accepted379ms34612 KiB
93Accepted532ms38520 KiB
94Accepted515ms37676 KiB
95Accepted501ms36148 KiB
96Accepted386ms39196 KiB
97Accepted624ms34488 KiB
98Accepted620ms34608 KiB
99Accepted625ms34612 KiB
100Accepted628ms34616 KiB
101Accepted630ms34612 KiB
102Accepted628ms34616 KiB
103Accepted883ms38336 KiB
104Accepted853ms36832 KiB
105Accepted832ms35896 KiB
106Accepted619ms41780 KiB
subtask80/21
107Accepted1ms316 KiB
108Time limit exceeded2.086s34056 KiB
109Time limit exceeded2.086s34036 KiB
110Time limit exceeded2.086s34108 KiB
111Time limit exceeded2.101s34056 KiB
112Time limit exceeded2.091s33904 KiB
113Time limit exceeded2.092s33856 KiB
114Time limit exceeded2.092s34096 KiB
115Accepted386ms34552 KiB
116Accepted386ms34612 KiB
117Accepted386ms34608 KiB
118Accepted386ms34456 KiB
119Accepted395ms34596 KiB
120Accepted395ms34636 KiB
121Time limit exceeded2.092s34020 KiB
122Time limit exceeded2.088s34100 KiB
subtask90/15
123Accepted1ms316 KiB
124Time limit exceeded2.086s34056 KiB
125Time limit exceeded2.094s46532 KiB
126Time limit exceeded2.092s34104 KiB
127Time limit exceeded2.094s35572 KiB
128Time limit exceeded2.094s46388 KiB
129Time limit exceeded2.082s42088 KiB
130Accepted391ms43828 KiB
131Accepted3ms820 KiB
132Accepted3ms1004 KiB
133Accepted3ms820 KiB
134Accepted3ms820 KiB
135Accepted3ms820 KiB
136Accepted3ms820 KiB
137Accepted3ms820 KiB
138Accepted3ms820 KiB
139Accepted3ms820 KiB
140Accepted158ms30776 KiB
141Accepted150ms30916 KiB
142Accepted156ms30720 KiB
143Accepted150ms30912 KiB
144Accepted157ms30948 KiB
145Accepted157ms30920 KiB
146Accepted234ms33844 KiB
147Accepted233ms33908 KiB
148Accepted225ms31796 KiB
149Accepted180ms41012 KiB
150Accepted959ms4916 KiB
151Accepted1.047s4808 KiB
152Accepted709ms4660 KiB
153Accepted703ms4888 KiB
154Accepted1.103s4548 KiB
155Accepted1.095s4404 KiB
156Accepted1.103s4540 KiB
157Accepted1.095s4408 KiB
158Accepted1.687s4848 KiB
159Accepted1.61s4836 KiB
160Accepted1.554s4840 KiB
161Accepted1.46s4656 KiB
162Accepted388ms34612 KiB
163Accepted382ms34612 KiB
164Accepted388ms34700 KiB
165Accepted381ms34620 KiB
166Accepted389ms34608 KiB
167Accepted379ms34612 KiB
168Accepted532ms38520 KiB
169Accepted515ms37676 KiB
170Accepted501ms36148 KiB
171Accepted386ms39196 KiB
172Accepted624ms34488 KiB
173Accepted620ms34608 KiB
174Accepted625ms34612 KiB
175Accepted628ms34616 KiB
176Accepted630ms34612 KiB
177Accepted628ms34616 KiB
178Accepted883ms38336 KiB
179Accepted853ms36832 KiB
180Accepted832ms35896 KiB
181Accepted619ms41780 KiB
182Time limit exceeded2.086s34036 KiB
183Time limit exceeded2.086s34108 KiB
184Time limit exceeded2.101s34056 KiB
185Time limit exceeded2.091s33904 KiB
186Time limit exceeded2.092s33856 KiB
187Time limit exceeded2.092s34096 KiB
188Accepted386ms34552 KiB
189Accepted386ms34612 KiB
190Accepted386ms34608 KiB
191Accepted386ms34456 KiB
192Accepted395ms34596 KiB
193Accepted395ms34636 KiB
194Time limit exceeded2.092s34020 KiB
195Time limit exceeded2.088s34100 KiB
196Time limit exceeded2.085s37220 KiB
197Time limit exceeded2.085s37088 KiB
198Time limit exceeded2.085s36896 KiB
199Time limit exceeded2.085s35124 KiB
200Time limit exceeded2.084s35124 KiB
201Time limit exceeded2.085s34872 KiB
202Time limit exceeded2.085s34508 KiB
203Time limit exceeded2.085s34284 KiB
204Time limit exceeded2.091s34188 KiB
205Time limit exceeded2.092s34100 KiB