167372025-05-11 22:35:59szilSiklóernyőzéscpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Time limit exceeded2.085s34356 KiB
subtask20/5
3Time limit exceeded2.088s44084 KiB
4Time limit exceeded2.085s34848 KiB
5Time limit exceeded2.086s36144 KiB
6Time limit exceeded2.086s44008 KiB
7Time limit exceeded2.085s40756 KiB
8Accepted270ms42548 KiB
subtask313/13
9Accepted2ms1084 KiB
10Accepted2ms1000 KiB
11Accepted2ms1012 KiB
12Accepted2ms820 KiB
13Accepted2ms820 KiB
14Accepted2ms892 KiB
15Accepted3ms820 KiB
16Accepted3ms820 KiB
17Accepted2ms884 KiB
subtask410/10
18Accepted2ms1084 KiB
19Accepted2ms1000 KiB
20Accepted2ms1012 KiB
21Accepted2ms820 KiB
22Accepted2ms820 KiB
23Accepted2ms892 KiB
24Accepted3ms820 KiB
25Accepted3ms820 KiB
26Accepted2ms884 KiB
27Accepted104ms31564 KiB
28Accepted97ms31668 KiB
29Accepted104ms31540 KiB
30Accepted98ms31520 KiB
31Accepted97ms31572 KiB
32Accepted104ms31540 KiB
33Accepted158ms33848 KiB
34Accepted151ms33984 KiB
35Accepted144ms32340 KiB
36Accepted136ms39296 KiB
subtask515/15
37Accepted2ms1084 KiB
38Accepted2ms1000 KiB
39Accepted2ms1012 KiB
40Accepted2ms820 KiB
41Accepted2ms820 KiB
42Accepted2ms892 KiB
43Accepted3ms820 KiB
44Accepted3ms820 KiB
45Accepted2ms884 KiB
46Accepted523ms4828 KiB
47Accepted526ms4824 KiB
48Accepted393ms5012 KiB
49Accepted393ms4876 KiB
50Accepted1.776s3812 KiB
51Accepted1.761s3840 KiB
52Accepted1.7s3788 KiB
53Accepted1.718s3636 KiB
54Accepted801ms4860 KiB
55Accepted772ms4824 KiB
56Accepted744ms4660 KiB
57Accepted699ms4664 KiB
subtask60/10
58Time limit exceeded2.082s34356 KiB
59Time limit exceeded2.082s34416 KiB
60Time limit exceeded2.082s34492 KiB
61Time limit exceeded2.084s34544 KiB
62Time limit exceeded2.085s34640 KiB
63Time limit exceeded2.086s34356 KiB
64Accepted338ms38428 KiB
65Accepted324ms37696 KiB
66Accepted316ms36660 KiB
67Accepted266ms38964 KiB
subtask70/11
68Accepted2ms1084 KiB
69Accepted2ms1000 KiB
70Accepted2ms1012 KiB
71Accepted2ms820 KiB
72Accepted2ms820 KiB
73Accepted2ms892 KiB
74Accepted3ms820 KiB
75Accepted3ms820 KiB
76Accepted2ms884 KiB
77Accepted104ms31564 KiB
78Accepted97ms31668 KiB
79Accepted104ms31540 KiB
80Accepted98ms31520 KiB
81Accepted97ms31572 KiB
82Accepted104ms31540 KiB
83Accepted158ms33848 KiB
84Accepted151ms33984 KiB
85Accepted144ms32340 KiB
86Accepted136ms39296 KiB
87Time limit exceeded2.082s34356 KiB
88Time limit exceeded2.082s34416 KiB
89Time limit exceeded2.082s34492 KiB
90Time limit exceeded2.084s34544 KiB
91Time limit exceeded2.085s34640 KiB
92Time limit exceeded2.086s34356 KiB
93Accepted338ms38428 KiB
94Accepted324ms37696 KiB
95Accepted316ms36660 KiB
96Accepted266ms38964 KiB
97Time limit exceeded2.095s34356 KiB
98Time limit exceeded2.095s34356 KiB
99Time limit exceeded2.095s34356 KiB
100Time limit exceeded2.095s34356 KiB
101Time limit exceeded2.095s34380 KiB
102Time limit exceeded2.095s34488 KiB
103Accepted517ms38192 KiB
104Accepted507ms37172 KiB
105Accepted486ms36660 KiB
106Accepted398ms41012 KiB
subtask80/21
107Accepted1ms500 KiB
108Time limit exceeded2.088s34356 KiB
109Time limit exceeded2.088s34116 KiB
110Time limit exceeded2.088s34316 KiB
111Time limit exceeded2.102s34356 KiB
112Time limit exceeded2.085s34140 KiB
113Time limit exceeded2.085s34244 KiB
114Time limit exceeded2.085s34312 KiB
115Time limit exceeded2.102s34356 KiB
116Time limit exceeded2.068s34356 KiB
117Time limit exceeded2.069s34528 KiB
118Time limit exceeded2.069s34444 KiB
119Time limit exceeded2.102s34512 KiB
120Time limit exceeded2.091s34612 KiB
121Time limit exceeded2.092s34356 KiB
122Time limit exceeded2.095s34360 KiB
subtask90/15
123Accepted1ms500 KiB
124Time limit exceeded2.088s34356 KiB
125Time limit exceeded2.088s44084 KiB
126Time limit exceeded2.085s34848 KiB
127Time limit exceeded2.086s36144 KiB
128Time limit exceeded2.086s44008 KiB
129Time limit exceeded2.085s40756 KiB
130Accepted270ms42548 KiB
131Accepted2ms1084 KiB
132Accepted2ms1000 KiB
133Accepted2ms1012 KiB
134Accepted2ms820 KiB
135Accepted2ms820 KiB
136Accepted2ms892 KiB
137Accepted3ms820 KiB
138Accepted3ms820 KiB
139Accepted2ms884 KiB
140Accepted104ms31564 KiB
141Accepted97ms31668 KiB
142Accepted104ms31540 KiB
143Accepted98ms31520 KiB
144Accepted97ms31572 KiB
145Accepted104ms31540 KiB
146Accepted158ms33848 KiB
147Accepted151ms33984 KiB
148Accepted144ms32340 KiB
149Accepted136ms39296 KiB
150Accepted523ms4828 KiB
151Accepted526ms4824 KiB
152Accepted393ms5012 KiB
153Accepted393ms4876 KiB
154Accepted1.776s3812 KiB
155Accepted1.761s3840 KiB
156Accepted1.7s3788 KiB
157Accepted1.718s3636 KiB
158Accepted801ms4860 KiB
159Accepted772ms4824 KiB
160Accepted744ms4660 KiB
161Accepted699ms4664 KiB
162Time limit exceeded2.082s34356 KiB
163Time limit exceeded2.082s34416 KiB
164Time limit exceeded2.082s34492 KiB
165Time limit exceeded2.084s34544 KiB
166Time limit exceeded2.085s34640 KiB
167Time limit exceeded2.086s34356 KiB
168Accepted338ms38428 KiB
169Accepted324ms37696 KiB
170Accepted316ms36660 KiB
171Accepted266ms38964 KiB
172Time limit exceeded2.095s34356 KiB
173Time limit exceeded2.095s34356 KiB
174Time limit exceeded2.095s34356 KiB
175Time limit exceeded2.095s34356 KiB
176Time limit exceeded2.095s34380 KiB
177Time limit exceeded2.095s34488 KiB
178Accepted517ms38192 KiB
179Accepted507ms37172 KiB
180Accepted486ms36660 KiB
181Accepted398ms41012 KiB
182Time limit exceeded2.088s34116 KiB
183Time limit exceeded2.088s34316 KiB
184Time limit exceeded2.102s34356 KiB
185Time limit exceeded2.085s34140 KiB
186Time limit exceeded2.085s34244 KiB
187Time limit exceeded2.085s34312 KiB
188Time limit exceeded2.102s34356 KiB
189Time limit exceeded2.068s34356 KiB
190Time limit exceeded2.069s34528 KiB
191Time limit exceeded2.069s34444 KiB
192Time limit exceeded2.102s34512 KiB
193Time limit exceeded2.091s34612 KiB
194Time limit exceeded2.092s34356 KiB
195Time limit exceeded2.095s34360 KiB
196Time limit exceeded2.091s37172 KiB
197Time limit exceeded2.092s37224 KiB
198Time limit exceeded2.092s36916 KiB
199Time limit exceeded2.091s35660 KiB
200Time limit exceeded2.088s35772 KiB
201Time limit exceeded2.089s35380 KiB
202Time limit exceeded2.088s34992 KiB
203Time limit exceeded2.088s34992 KiB
204Time limit exceeded2.088s34952 KiB
205Time limit exceeded2.088s34868 KiB