167582025-05-12 10:42:14szilSiklóernyőzéscpp17Time limit exceeded 80/1002.092s23920 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 v) {
            mx  += v;
            lazy += v;
        }
    };

    int n, h;
    vector<node> tree;

    segtree2() {}
    segtree2(int _n) : n(_n) {
        h = sizeof(int) * 8 - __builtin_clz(n);
        tree.resize(2 * n);
    }

    void apply(int p, int v) {
        tree[p].apply(v);
    }

    void build(int p) {
        while (p > 1) {
            p >>= 1;
            tree[p].mx = max(tree[p<<1].mx, tree[p<<1|1].mx) + tree[p].lazy;
        }
    }

    void push(int p) {
        for (int s = h; s > 0; --s) {
            int i = p >> s;
            if (tree[i].lazy) {
                tree[i<<1].apply(tree[i].lazy);
                tree[i<<1|1].apply(tree[i].lazy);
                tree[i].lazy = 0;
            }
        }
    }

    void upd_add(int a, int b, int c, int l, int r, int v) {
        if (l > r) return;
        int l0 = l += n, r0 = ++r += n;
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) apply(l++, v);
            if (r & 1) apply(--r, v);
        }
        build(l0);
        build(r0 - 1);
    }

    int qry(int a, int b, int c, int l, int r) {
        if (l > r) return 0;
        int res = 0;
        int l0 = l += n, r0 = ++r += n;
        push(l0);
        push(r0 - 1);
        for (; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, tree[l++].mx);
            if (r & 1) res = max(res, tree[--r].mx);
        }
        return res;
    }
};

int a[MAXN], n, q, il[MAXN], ir[MAXN], ans[MAXN], depth[MAXN], max_depth = 0;
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);
    depth[u] = d;
    max_depth = max(max_depth, d);
    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);
    bool is_subtask7 = max_depth <= 70;

    vector<array<int, 3>> qrys(q);
    auto upd = [&](auto &&self, int l, int r, bool go_right, int sgn, int u = -1) -> void {
        if (l > r) return;
        if (u == -1) u = st_max.qry(l, r);
        int nl = l, nr = r;
        if (go_right) nl = u+1;
        else nr = u-1;
        int v = st_max.qry(nl, nr);
        int outside = depth[v] - depth[u] - 1;
        st_depth.upd_add(1, 1, n, nl, nr, outside * sgn);
        self(self, nl, nr, go_right, sgn, v);
    };

    for (int i = 0; i < q; i++) {
        cin >> qrys[i][0] >> qrys[i][1];
        qrys[i][2] = i+1;
    }
    if (is_subtask7) {
        vector<vector<pair<int, int>>> mp(n+1);
        for (int i = 0; i < q; i++) {
            mp[qrys[i][1]].emplace_back(qrys[i][0], qrys[i][2]);
        }
        for (int i = 1; i <= n; i++) {
            st_depth.upd_add(1, 1, n, il[i], ir[i], 1);
            vector<int> root_depth(mp[i].size());
            for (int j = 0; j < mp[i].size(); j++) {
                root_depth[j] = st_depth.qry(1, 1, n, st_max.qry(mp[i][j].first, i), st_max.qry(mp[i][j].first, i));
            }
            for (int j = 0; j < mp[i].size(); j++) {
                auto [l, idx] = mp[i][j];
                upd(upd, l, i, 0, -1);
                ans[idx] = st_depth.qry(1, 1, n, l, i)-root_depth[j];
                upd(upd, l, i, 0, 1);
            }
        }
        
    } else {
        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
2Accepted1.697s21556 KiB
subtask20/5
3Time limit exceeded2.091s22348 KiB
4Time limit exceeded2.091s12852 KiB
5Time limit exceeded2.091s14132 KiB
6Time limit exceeded2.092s22068 KiB
7Time limit exceeded2.078s18952 KiB
8Accepted268ms20532 KiB
subtask313/13
9Accepted2ms756 KiB
10Accepted2ms756 KiB
11Accepted2ms564 KiB
12Accepted2ms564 KiB
13Accepted2ms564 KiB
14Accepted2ms564 KiB
15Accepted2ms564 KiB
16Accepted2ms568 KiB
17Accepted2ms564 KiB
subtask410/10
18Accepted2ms756 KiB
19Accepted2ms756 KiB
20Accepted2ms564 KiB
21Accepted2ms564 KiB
22Accepted2ms564 KiB
23Accepted2ms564 KiB
24Accepted2ms564 KiB
25Accepted2ms568 KiB
26Accepted2ms564 KiB
27Accepted85ms14628 KiB
28Accepted82ms14512 KiB
29Accepted82ms14388 KiB
30Accepted86ms14384 KiB
31Accepted86ms14396 KiB
32Accepted82ms14388 KiB
33Accepted116ms12084 KiB
34Accepted123ms12084 KiB
35Accepted118ms10548 KiB
36Accepted123ms17204 KiB
subtask515/15
37Accepted2ms756 KiB
38Accepted2ms756 KiB
39Accepted2ms564 KiB
40Accepted2ms564 KiB
41Accepted2ms564 KiB
42Accepted2ms564 KiB
43Accepted2ms564 KiB
44Accepted2ms568 KiB
45Accepted2ms564 KiB
46Accepted495ms4660 KiB
47Accepted527ms4500 KiB
48Accepted370ms4536 KiB
49Accepted370ms4404 KiB
50Accepted699ms6568 KiB
51Accepted746ms6196 KiB
52Accepted690ms6196 KiB
53Accepted732ms6276 KiB
54Accepted497ms4404 KiB
55Accepted486ms4404 KiB
56Accepted477ms4408 KiB
57Accepted467ms4404 KiB
subtask610/10
58Accepted1.253s23860 KiB
59Accepted1.222s23908 KiB
60Accepted1.238s23824 KiB
61Accepted1.037s23920 KiB
62Accepted744ms23704 KiB
63Accepted1.062s23860 KiB
64Accepted263ms16500 KiB
65Accepted263ms15892 KiB
66Accepted257ms14648 KiB
67Accepted256ms17112 KiB
subtask711/11
68Accepted2ms756 KiB
69Accepted2ms756 KiB
70Accepted2ms564 KiB
71Accepted2ms564 KiB
72Accepted2ms564 KiB
73Accepted2ms564 KiB
74Accepted2ms564 KiB
75Accepted2ms568 KiB
76Accepted2ms564 KiB
77Accepted85ms14628 KiB
78Accepted82ms14512 KiB
79Accepted82ms14388 KiB
80Accepted86ms14384 KiB
81Accepted86ms14396 KiB
82Accepted82ms14388 KiB
83Accepted116ms12084 KiB
84Accepted123ms12084 KiB
85Accepted118ms10548 KiB
86Accepted123ms17204 KiB
87Accepted1.253s23860 KiB
88Accepted1.222s23908 KiB
89Accepted1.238s23824 KiB
90Accepted1.037s23920 KiB
91Accepted744ms23704 KiB
92Accepted1.062s23860 KiB
93Accepted263ms16500 KiB
94Accepted263ms15892 KiB
95Accepted257ms14648 KiB
96Accepted256ms17112 KiB
97Accepted1.208s21260 KiB
98Accepted1.259s21300 KiB
99Accepted1.192s21556 KiB
100Accepted1.156s21240 KiB
101Accepted1.292s21300 KiB
102Accepted1.213s21376 KiB
103Accepted354ms16440 KiB
104Accepted363ms15288 KiB
105Accepted358ms14584 KiB
106Accepted351ms18996 KiB
subtask821/21
107Accepted1ms316 KiB
108Accepted1.684s21556 KiB
109Accepted1.996s21556 KiB
110Accepted1.718s21452 KiB
111Accepted1.827s21576 KiB
112Accepted1.883s21556 KiB
113Accepted1.828s21556 KiB
114Accepted1.779s21556 KiB
115Accepted1.059s23888 KiB
116Accepted842ms23892 KiB
117Accepted970ms23860 KiB
118Accepted810ms23860 KiB
119Accepted1.029s23860 KiB
120Accepted795ms23860 KiB
121Accepted1.728s21556 KiB
122Accepted1.715s21556 KiB
subtask90/15
123Accepted1ms316 KiB
124Accepted1.684s21556 KiB
125Time limit exceeded2.091s22348 KiB
126Time limit exceeded2.091s12852 KiB
127Time limit exceeded2.091s14132 KiB
128Time limit exceeded2.092s22068 KiB
129Time limit exceeded2.078s18952 KiB
130Accepted268ms20532 KiB
131Accepted2ms756 KiB
132Accepted2ms756 KiB
133Accepted2ms564 KiB
134Accepted2ms564 KiB
135Accepted2ms564 KiB
136Accepted2ms564 KiB
137Accepted2ms564 KiB
138Accepted2ms568 KiB
139Accepted2ms564 KiB
140Accepted85ms14628 KiB
141Accepted82ms14512 KiB
142Accepted82ms14388 KiB
143Accepted86ms14384 KiB
144Accepted86ms14396 KiB
145Accepted82ms14388 KiB
146Accepted116ms12084 KiB
147Accepted123ms12084 KiB
148Accepted118ms10548 KiB
149Accepted123ms17204 KiB
150Accepted495ms4660 KiB
151Accepted527ms4500 KiB
152Accepted370ms4536 KiB
153Accepted370ms4404 KiB
154Accepted699ms6568 KiB
155Accepted746ms6196 KiB
156Accepted690ms6196 KiB
157Accepted732ms6276 KiB
158Accepted497ms4404 KiB
159Accepted486ms4404 KiB
160Accepted477ms4408 KiB
161Accepted467ms4404 KiB
162Accepted1.253s23860 KiB
163Accepted1.222s23908 KiB
164Accepted1.238s23824 KiB
165Accepted1.037s23920 KiB
166Accepted744ms23704 KiB
167Accepted1.062s23860 KiB
168Accepted263ms16500 KiB
169Accepted263ms15892 KiB
170Accepted257ms14648 KiB
171Accepted256ms17112 KiB
172Accepted1.208s21260 KiB
173Accepted1.259s21300 KiB
174Accepted1.192s21556 KiB
175Accepted1.156s21240 KiB
176Accepted1.292s21300 KiB
177Accepted1.213s21376 KiB
178Accepted354ms16440 KiB
179Accepted363ms15288 KiB
180Accepted358ms14584 KiB
181Accepted351ms18996 KiB
182Accepted1.996s21556 KiB
183Accepted1.718s21452 KiB
184Accepted1.827s21576 KiB
185Accepted1.883s21556 KiB
186Accepted1.828s21556 KiB
187Accepted1.779s21556 KiB
188Accepted1.059s23888 KiB
189Accepted842ms23892 KiB
190Accepted970ms23860 KiB
191Accepted810ms23860 KiB
192Accepted1.029s23860 KiB
193Accepted795ms23860 KiB
194Accepted1.728s21556 KiB
195Accepted1.715s21556 KiB
196Time limit exceeded2.091s15156 KiB
197Time limit exceeded2.091s15156 KiB
198Time limit exceeded2.091s15024 KiB
199Time limit exceeded2.091s13800 KiB
200Time limit exceeded2.082s13652 KiB
201Time limit exceeded2.082s13620 KiB
202Time limit exceeded2.082s13112 KiB
203Time limit exceeded2.084s13108 KiB
204Time limit exceeded2.079s12852 KiB
205Time limit exceeded2.079s12992 KiB