167362025-05-11 22:34:26szilSiklóernyőzéscpp17Időlimit túllépés 0/1002.101s31540 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(8*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) + u.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;
        } 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.088s21808 KiB
subtask20/5
3Időlimit túllépés2.085s31540 KiB
4Időlimit túllépés2.084s22324 KiB
5Időlimit túllépés2.085s23604 KiB
6Időlimit túllépés2.085s31540 KiB
7Időlimit túllépés2.089s28152 KiB
8Elfogadva277ms30004 KiB
subtask30/13
9Elfogadva2ms564 KiB
10Elfogadva3ms564 KiB
11Elfogadva2ms572 KiB
12Elfogadva2ms756 KiB
13Elfogadva2ms564 KiB
14Elfogadva2ms564 KiB
15Hibás válasz3ms732 KiB
16Hibás válasz3ms752 KiB
17Elfogadva2ms820 KiB
subtask40/10
18Elfogadva2ms564 KiB
19Elfogadva3ms564 KiB
20Elfogadva2ms572 KiB
21Elfogadva2ms756 KiB
22Elfogadva2ms564 KiB
23Elfogadva2ms564 KiB
24Hibás válasz3ms732 KiB
25Hibás válasz3ms752 KiB
26Elfogadva2ms820 KiB
27Elfogadva94ms19024 KiB
28Elfogadva94ms19188 KiB
29Elfogadva94ms18976 KiB
30Elfogadva90ms19208 KiB
31Elfogadva90ms18996 KiB
32Elfogadva93ms18996 KiB
33Hibás válasz150ms21556 KiB
34Hibás válasz148ms21500 KiB
35Hibás válasz141ms19776 KiB
36Elfogadva129ms26676 KiB
subtask50/15
37Elfogadva2ms564 KiB
38Elfogadva3ms564 KiB
39Elfogadva2ms572 KiB
40Elfogadva2ms756 KiB
41Elfogadva2ms564 KiB
42Elfogadva2ms564 KiB
43Hibás válasz3ms732 KiB
44Hibás válasz3ms752 KiB
45Elfogadva2ms820 KiB
46Hibás válasz527ms4756 KiB
47Hibás válasz500ms4660 KiB
48Hibás válasz395ms4660 KiB
49Hibás válasz391ms4660 KiB
50Hibás válasz1.779s3628 KiB
51Hibás válasz1.763s3508 KiB
52Hibás válasz1.703s3568 KiB
53Hibás válasz1.715s3884 KiB
54Hibás válasz782ms4652 KiB
55Hibás válasz754ms4640 KiB
56Hibás válasz722ms4660 KiB
57Hibás válasz680ms4648 KiB
subtask60/10
58Időlimit túllépés2.088s21796 KiB
59Időlimit túllépés2.088s22056 KiB
60Időlimit túllépés2.088s21812 KiB
61Időlimit túllépés2.088s22068 KiB
62Időlimit túllépés2.086s22000 KiB
63Időlimit túllépés2.088s22064 KiB
64Hibás válasz331ms25908 KiB
65Hibás válasz321ms25368 KiB
66Hibás válasz314ms24120 KiB
67Hibás válasz256ms26480 KiB
subtask70/11
68Elfogadva2ms564 KiB
69Elfogadva3ms564 KiB
70Elfogadva2ms572 KiB
71Elfogadva2ms756 KiB
72Elfogadva2ms564 KiB
73Elfogadva2ms564 KiB
74Hibás válasz3ms732 KiB
75Hibás válasz3ms752 KiB
76Elfogadva2ms820 KiB
77Elfogadva94ms19024 KiB
78Elfogadva94ms19188 KiB
79Elfogadva94ms18976 KiB
80Elfogadva90ms19208 KiB
81Elfogadva90ms18996 KiB
82Elfogadva93ms18996 KiB
83Hibás válasz150ms21556 KiB
84Hibás válasz148ms21500 KiB
85Hibás válasz141ms19776 KiB
86Elfogadva129ms26676 KiB
87Időlimit túllépés2.088s21796 KiB
88Időlimit túllépés2.088s22056 KiB
89Időlimit túllépés2.088s21812 KiB
90Időlimit túllépés2.088s22068 KiB
91Időlimit túllépés2.086s22000 KiB
92Időlimit túllépés2.088s22064 KiB
93Hibás válasz331ms25908 KiB
94Hibás válasz321ms25368 KiB
95Hibás válasz314ms24120 KiB
96Hibás válasz256ms26480 KiB
97Időlimit túllépés2.085s21812 KiB
98Időlimit túllépés2.085s21764 KiB
99Időlimit túllépés2.085s21812 KiB
100Időlimit túllépés2.085s21804 KiB
101Időlimit túllépés2.085s21924 KiB
102Időlimit túllépés2.086s21940 KiB
103Hibás válasz515ms25908 KiB
104Hibás válasz492ms24628 KiB
105Hibás válasz481ms24116 KiB
106Hibás válasz391ms28472 KiB
subtask80/21
107Elfogadva1ms500 KiB
108Időlimit túllépés2.088s21812 KiB
109Időlimit túllépés2.088s21812 KiB
110Időlimit túllépés2.088s21640 KiB
111Időlimit túllépés2.101s21744 KiB
112Időlimit túllépés2.085s21692 KiB
113Időlimit túllépés2.085s21804 KiB
114Időlimit túllépés2.084s21748 KiB
115Időlimit túllépés2.101s22124 KiB
116Időlimit túllépés2.088s22068 KiB
117Időlimit túllépés2.088s21824 KiB
118Időlimit túllépés2.088s22068 KiB
119Időlimit túllépés2.101s21812 KiB
120Időlimit túllépés2.091s21996 KiB
121Időlimit túllépés2.089s21812 KiB
122Időlimit túllépés2.091s21860 KiB
subtask90/15
123Elfogadva1ms500 KiB
124Időlimit túllépés2.088s21812 KiB
125Időlimit túllépés2.085s31540 KiB
126Időlimit túllépés2.084s22324 KiB
127Időlimit túllépés2.085s23604 KiB
128Időlimit túllépés2.085s31540 KiB
129Időlimit túllépés2.089s28152 KiB
130Elfogadva277ms30004 KiB
131Elfogadva2ms564 KiB
132Elfogadva3ms564 KiB
133Elfogadva2ms572 KiB
134Elfogadva2ms756 KiB
135Elfogadva2ms564 KiB
136Elfogadva2ms564 KiB
137Hibás válasz3ms732 KiB
138Hibás válasz3ms752 KiB
139Elfogadva2ms820 KiB
140Elfogadva94ms19024 KiB
141Elfogadva94ms19188 KiB
142Elfogadva94ms18976 KiB
143Elfogadva90ms19208 KiB
144Elfogadva90ms18996 KiB
145Elfogadva93ms18996 KiB
146Hibás válasz150ms21556 KiB
147Hibás válasz148ms21500 KiB
148Hibás válasz141ms19776 KiB
149Elfogadva129ms26676 KiB
150Hibás válasz527ms4756 KiB
151Hibás válasz500ms4660 KiB
152Hibás válasz395ms4660 KiB
153Hibás válasz391ms4660 KiB
154Hibás válasz1.779s3628 KiB
155Hibás válasz1.763s3508 KiB
156Hibás válasz1.703s3568 KiB
157Hibás válasz1.715s3884 KiB
158Hibás válasz782ms4652 KiB
159Hibás válasz754ms4640 KiB
160Hibás válasz722ms4660 KiB
161Hibás válasz680ms4648 KiB
162Időlimit túllépés2.088s21796 KiB
163Időlimit túllépés2.088s22056 KiB
164Időlimit túllépés2.088s21812 KiB
165Időlimit túllépés2.088s22068 KiB
166Időlimit túllépés2.086s22000 KiB
167Időlimit túllépés2.088s22064 KiB
168Hibás válasz331ms25908 KiB
169Hibás válasz321ms25368 KiB
170Hibás válasz314ms24120 KiB
171Hibás válasz256ms26480 KiB
172Időlimit túllépés2.085s21812 KiB
173Időlimit túllépés2.085s21764 KiB
174Időlimit túllépés2.085s21812 KiB
175Időlimit túllépés2.085s21804 KiB
176Időlimit túllépés2.085s21924 KiB
177Időlimit túllépés2.086s21940 KiB
178Hibás válasz515ms25908 KiB
179Hibás válasz492ms24628 KiB
180Hibás válasz481ms24116 KiB
181Hibás válasz391ms28472 KiB
182Időlimit túllépés2.088s21812 KiB
183Időlimit túllépés2.088s21640 KiB
184Időlimit túllépés2.101s21744 KiB
185Időlimit túllépés2.085s21692 KiB
186Időlimit túllépés2.085s21804 KiB
187Időlimit túllépés2.084s21748 KiB
188Időlimit túllépés2.101s22124 KiB
189Időlimit túllépés2.088s22068 KiB
190Időlimit túllépés2.088s21824 KiB
191Időlimit túllépés2.088s22068 KiB
192Időlimit túllépés2.101s21812 KiB
193Időlimit túllépés2.091s21996 KiB
194Időlimit túllépés2.089s21812 KiB
195Időlimit túllépés2.091s21860 KiB
196Időlimit túllépés2.085s24460 KiB
197Időlimit túllépés2.086s24700 KiB
198Időlimit túllépés2.085s24312 KiB
199Időlimit túllépés2.085s23204 KiB
200Időlimit túllépés2.094s23092 KiB
201Időlimit túllépés2.092s22976 KiB
202Időlimit túllépés2.092s22512 KiB
203Időlimit túllépés2.092s22520 KiB
204Időlimit túllépés2.086s22324 KiB
205Időlimit túllépés2.088s22172 KiB