167372025-05-11 22:35:59szilSiklóernyőzéscpp17Időlimit túllépés 38/1002.102s44084 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 pull(int v) {

        node &u = tree[v];
        node &l = tree[2*v];
        node &r = tree[2*v+1];

        u.mx = max(l.mx + l.lazy, r.mx + r.lazy);
    }

    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 + tree[v].lazy;
        } 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)) + tree[v].lazy;
        }
    }
};

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);
    };

    if (is_subtask7) {
        for (int i = 1; i <= n; i++) st_depth.upd_add(1, 1, n, i, i, depth[i]);
    }

    for (int i = 0; i < q; i++) {
        if (is_subtask7) {
            int l, r; cin >> l >> r;
            upd(upd, l, r, 0, -1);
            upd(upd, l, r, 1, -1);
            cout << st_depth.qry(1, 1, n, l, r)-depth[st_max.qry(l, r)] << "\n";
            upd(upd, l, r, 0, 1);
            upd(upd, l, r, 1, 1);
        } else {
            cin >> qrys[i][0] >> qrys[i][1];
            qrys[i][2] = i+1;
        }
    }
    if (is_subtask7) return;
    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
1Elfogadva1ms316 KiB
2Időlimit túllépés2.085s34356 KiB
subtask20/5
3Időlimit túllépés2.088s44084 KiB
4Időlimit túllépés2.085s34848 KiB
5Időlimit túllépés2.086s36144 KiB
6Időlimit túllépés2.086s44008 KiB
7Időlimit túllépés2.085s40756 KiB
8Elfogadva270ms42548 KiB
subtask313/13
9Elfogadva2ms1084 KiB
10Elfogadva2ms1000 KiB
11Elfogadva2ms1012 KiB
12Elfogadva2ms820 KiB
13Elfogadva2ms820 KiB
14Elfogadva2ms892 KiB
15Elfogadva3ms820 KiB
16Elfogadva3ms820 KiB
17Elfogadva2ms884 KiB
subtask410/10
18Elfogadva2ms1084 KiB
19Elfogadva2ms1000 KiB
20Elfogadva2ms1012 KiB
21Elfogadva2ms820 KiB
22Elfogadva2ms820 KiB
23Elfogadva2ms892 KiB
24Elfogadva3ms820 KiB
25Elfogadva3ms820 KiB
26Elfogadva2ms884 KiB
27Elfogadva104ms31564 KiB
28Elfogadva97ms31668 KiB
29Elfogadva104ms31540 KiB
30Elfogadva98ms31520 KiB
31Elfogadva97ms31572 KiB
32Elfogadva104ms31540 KiB
33Elfogadva158ms33848 KiB
34Elfogadva151ms33984 KiB
35Elfogadva144ms32340 KiB
36Elfogadva136ms39296 KiB
subtask515/15
37Elfogadva2ms1084 KiB
38Elfogadva2ms1000 KiB
39Elfogadva2ms1012 KiB
40Elfogadva2ms820 KiB
41Elfogadva2ms820 KiB
42Elfogadva2ms892 KiB
43Elfogadva3ms820 KiB
44Elfogadva3ms820 KiB
45Elfogadva2ms884 KiB
46Elfogadva523ms4828 KiB
47Elfogadva526ms4824 KiB
48Elfogadva393ms5012 KiB
49Elfogadva393ms4876 KiB
50Elfogadva1.776s3812 KiB
51Elfogadva1.761s3840 KiB
52Elfogadva1.7s3788 KiB
53Elfogadva1.718s3636 KiB
54Elfogadva801ms4860 KiB
55Elfogadva772ms4824 KiB
56Elfogadva744ms4660 KiB
57Elfogadva699ms4664 KiB
subtask60/10
58Időlimit túllépés2.082s34356 KiB
59Időlimit túllépés2.082s34416 KiB
60Időlimit túllépés2.082s34492 KiB
61Időlimit túllépés2.084s34544 KiB
62Időlimit túllépés2.085s34640 KiB
63Időlimit túllépés2.086s34356 KiB
64Elfogadva338ms38428 KiB
65Elfogadva324ms37696 KiB
66Elfogadva316ms36660 KiB
67Elfogadva266ms38964 KiB
subtask70/11
68Elfogadva2ms1084 KiB
69Elfogadva2ms1000 KiB
70Elfogadva2ms1012 KiB
71Elfogadva2ms820 KiB
72Elfogadva2ms820 KiB
73Elfogadva2ms892 KiB
74Elfogadva3ms820 KiB
75Elfogadva3ms820 KiB
76Elfogadva2ms884 KiB
77Elfogadva104ms31564 KiB
78Elfogadva97ms31668 KiB
79Elfogadva104ms31540 KiB
80Elfogadva98ms31520 KiB
81Elfogadva97ms31572 KiB
82Elfogadva104ms31540 KiB
83Elfogadva158ms33848 KiB
84Elfogadva151ms33984 KiB
85Elfogadva144ms32340 KiB
86Elfogadva136ms39296 KiB
87Időlimit túllépés2.082s34356 KiB
88Időlimit túllépés2.082s34416 KiB
89Időlimit túllépés2.082s34492 KiB
90Időlimit túllépés2.084s34544 KiB
91Időlimit túllépés2.085s34640 KiB
92Időlimit túllépés2.086s34356 KiB
93Elfogadva338ms38428 KiB
94Elfogadva324ms37696 KiB
95Elfogadva316ms36660 KiB
96Elfogadva266ms38964 KiB
97Időlimit túllépés2.095s34356 KiB
98Időlimit túllépés2.095s34356 KiB
99Időlimit túllépés2.095s34356 KiB
100Időlimit túllépés2.095s34356 KiB
101Időlimit túllépés2.095s34380 KiB
102Időlimit túllépés2.095s34488 KiB
103Elfogadva517ms38192 KiB
104Elfogadva507ms37172 KiB
105Elfogadva486ms36660 KiB
106Elfogadva398ms41012 KiB
subtask80/21
107Elfogadva1ms500 KiB
108Időlimit túllépés2.088s34356 KiB
109Időlimit túllépés2.088s34116 KiB
110Időlimit túllépés2.088s34316 KiB
111Időlimit túllépés2.102s34356 KiB
112Időlimit túllépés2.085s34140 KiB
113Időlimit túllépés2.085s34244 KiB
114Időlimit túllépés2.085s34312 KiB
115Időlimit túllépés2.102s34356 KiB
116Időlimit túllépés2.068s34356 KiB
117Időlimit túllépés2.069s34528 KiB
118Időlimit túllépés2.069s34444 KiB
119Időlimit túllépés2.102s34512 KiB
120Időlimit túllépés2.091s34612 KiB
121Időlimit túllépés2.092s34356 KiB
122Időlimit túllépés2.095s34360 KiB
subtask90/15
123Elfogadva1ms500 KiB
124Időlimit túllépés2.088s34356 KiB
125Időlimit túllépés2.088s44084 KiB
126Időlimit túllépés2.085s34848 KiB
127Időlimit túllépés2.086s36144 KiB
128Időlimit túllépés2.086s44008 KiB
129Időlimit túllépés2.085s40756 KiB
130Elfogadva270ms42548 KiB
131Elfogadva2ms1084 KiB
132Elfogadva2ms1000 KiB
133Elfogadva2ms1012 KiB
134Elfogadva2ms820 KiB
135Elfogadva2ms820 KiB
136Elfogadva2ms892 KiB
137Elfogadva3ms820 KiB
138Elfogadva3ms820 KiB
139Elfogadva2ms884 KiB
140Elfogadva104ms31564 KiB
141Elfogadva97ms31668 KiB
142Elfogadva104ms31540 KiB
143Elfogadva98ms31520 KiB
144Elfogadva97ms31572 KiB
145Elfogadva104ms31540 KiB
146Elfogadva158ms33848 KiB
147Elfogadva151ms33984 KiB
148Elfogadva144ms32340 KiB
149Elfogadva136ms39296 KiB
150Elfogadva523ms4828 KiB
151Elfogadva526ms4824 KiB
152Elfogadva393ms5012 KiB
153Elfogadva393ms4876 KiB
154Elfogadva1.776s3812 KiB
155Elfogadva1.761s3840 KiB
156Elfogadva1.7s3788 KiB
157Elfogadva1.718s3636 KiB
158Elfogadva801ms4860 KiB
159Elfogadva772ms4824 KiB
160Elfogadva744ms4660 KiB
161Elfogadva699ms4664 KiB
162Időlimit túllépés2.082s34356 KiB
163Időlimit túllépés2.082s34416 KiB
164Időlimit túllépés2.082s34492 KiB
165Időlimit túllépés2.084s34544 KiB
166Időlimit túllépés2.085s34640 KiB
167Időlimit túllépés2.086s34356 KiB
168Elfogadva338ms38428 KiB
169Elfogadva324ms37696 KiB
170Elfogadva316ms36660 KiB
171Elfogadva266ms38964 KiB
172Időlimit túllépés2.095s34356 KiB
173Időlimit túllépés2.095s34356 KiB
174Időlimit túllépés2.095s34356 KiB
175Időlimit túllépés2.095s34356 KiB
176Időlimit túllépés2.095s34380 KiB
177Időlimit túllépés2.095s34488 KiB
178Elfogadva517ms38192 KiB
179Elfogadva507ms37172 KiB
180Elfogadva486ms36660 KiB
181Elfogadva398ms41012 KiB
182Időlimit túllépés2.088s34116 KiB
183Időlimit túllépés2.088s34316 KiB
184Időlimit túllépés2.102s34356 KiB
185Időlimit túllépés2.085s34140 KiB
186Időlimit túllépés2.085s34244 KiB
187Időlimit túllépés2.085s34312 KiB
188Időlimit túllépés2.102s34356 KiB
189Időlimit túllépés2.068s34356 KiB
190Időlimit túllépés2.069s34528 KiB
191Időlimit túllépés2.069s34444 KiB
192Időlimit túllépés2.102s34512 KiB
193Időlimit túllépés2.091s34612 KiB
194Időlimit túllépés2.092s34356 KiB
195Időlimit túllépés2.095s34360 KiB
196Időlimit túllépés2.091s37172 KiB
197Időlimit túllépés2.092s37224 KiB
198Időlimit túllépés2.092s36916 KiB
199Időlimit túllépés2.091s35660 KiB
200Időlimit túllépés2.088s35772 KiB
201Időlimit túllépés2.089s35380 KiB
202Időlimit túllépés2.088s34992 KiB
203Időlimit túllépés2.088s34992 KiB
204Időlimit túllépés2.088s34952 KiB
205Időlimit túllépés2.088s34868 KiB