167572025-05-12 10:30:05szilSiklóernyőzéscpp17Hibás válasz 33/1002.095s23864 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);
            for (auto [l, idx] : mp[i]) {
                upd(upd, l, i, 0, -1);
                ans[idx] = st_depth.qry(1, 1, n, l, i)-1;
                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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms508 KiB
2Hibás válasz1.565s21600 KiB
subtask20/5
3Időlimit túllépés2.081s22336 KiB
4Időlimit túllépés2.081s12904 KiB
5Időlimit túllépés2.082s14132 KiB
6Időlimit túllépés2.082s22068 KiB
7Időlimit túllépés2.085s18740 KiB
8Elfogadva263ms20548 KiB
subtask313/13
9Elfogadva2ms564 KiB
10Elfogadva2ms564 KiB
11Elfogadva2ms748 KiB
12Elfogadva2ms564 KiB
13Elfogadva2ms564 KiB
14Elfogadva2ms660 KiB
15Elfogadva2ms540 KiB
16Elfogadva2ms388 KiB
17Elfogadva2ms564 KiB
subtask410/10
18Elfogadva2ms564 KiB
19Elfogadva2ms564 KiB
20Elfogadva2ms748 KiB
21Elfogadva2ms564 KiB
22Elfogadva2ms564 KiB
23Elfogadva2ms660 KiB
24Elfogadva2ms540 KiB
25Elfogadva2ms388 KiB
26Elfogadva2ms564 KiB
27Elfogadva85ms14404 KiB
28Elfogadva82ms14408 KiB
29Elfogadva82ms14504 KiB
30Elfogadva85ms14524 KiB
31Elfogadva82ms14388 KiB
32Elfogadva85ms14388 KiB
33Elfogadva114ms12004 KiB
34Elfogadva115ms12088 KiB
35Elfogadva112ms10600 KiB
36Elfogadva119ms17216 KiB
subtask50/15
37Elfogadva2ms564 KiB
38Elfogadva2ms564 KiB
39Elfogadva2ms748 KiB
40Elfogadva2ms564 KiB
41Elfogadva2ms564 KiB
42Elfogadva2ms660 KiB
43Elfogadva2ms540 KiB
44Elfogadva2ms388 KiB
45Elfogadva2ms564 KiB
46Elfogadva467ms4652 KiB
47Elfogadva495ms4404 KiB
48Elfogadva354ms4404 KiB
49Elfogadva352ms4540 KiB
50Hibás válasz657ms6196 KiB
51Hibás válasz698ms6476 KiB
52Hibás válasz647ms6452 KiB
53Hibás válasz685ms6280 KiB
54Elfogadva474ms4404 KiB
55Elfogadva460ms4404 KiB
56Elfogadva453ms4512 KiB
57Elfogadva442ms4400 KiB
subtask610/10
58Elfogadva1.243s23720 KiB
59Elfogadva1.212s23732 KiB
60Elfogadva1.225s23776 KiB
61Elfogadva1.023s23844 KiB
62Elfogadva718ms23812 KiB
63Elfogadva1.062s23744 KiB
64Elfogadva257ms16380 KiB
65Elfogadva263ms15924 KiB
66Elfogadva261ms14644 KiB
67Elfogadva254ms16964 KiB
subtask70/11
68Elfogadva2ms564 KiB
69Elfogadva2ms564 KiB
70Elfogadva2ms748 KiB
71Elfogadva2ms564 KiB
72Elfogadva2ms564 KiB
73Elfogadva2ms660 KiB
74Elfogadva2ms540 KiB
75Elfogadva2ms388 KiB
76Elfogadva2ms564 KiB
77Elfogadva85ms14404 KiB
78Elfogadva82ms14408 KiB
79Elfogadva82ms14504 KiB
80Elfogadva85ms14524 KiB
81Elfogadva82ms14388 KiB
82Elfogadva85ms14388 KiB
83Elfogadva114ms12004 KiB
84Elfogadva115ms12088 KiB
85Elfogadva112ms10600 KiB
86Elfogadva119ms17216 KiB
87Elfogadva1.243s23720 KiB
88Elfogadva1.212s23732 KiB
89Elfogadva1.225s23776 KiB
90Elfogadva1.023s23844 KiB
91Elfogadva718ms23812 KiB
92Elfogadva1.062s23744 KiB
93Elfogadva257ms16380 KiB
94Elfogadva263ms15924 KiB
95Elfogadva261ms14644 KiB
96Elfogadva254ms16964 KiB
97Elfogadva1.185s21144 KiB
98Hibás válasz1.233s21408 KiB
99Hibás válasz1.161s21156 KiB
100Hibás válasz1.129s21416 KiB
101Elfogadva1.264s21360 KiB
102Hibás válasz1.189s21156 KiB
103Elfogadva344ms16332 KiB
104Elfogadva352ms15168 KiB
105Elfogadva349ms14640 KiB
106Elfogadva340ms18996 KiB
subtask80/21
107Elfogadva1ms316 KiB
108Hibás válasz1.575s21556 KiB
109Hibás válasz1.876s21568 KiB
110Hibás válasz1.646s21556 KiB
111Hibás válasz1.671s21556 KiB
112Hibás válasz1.761s21556 KiB
113Hibás válasz1.677s21556 KiB
114Hibás válasz1.597s21520 KiB
115Elfogadva1.044s23864 KiB
116Elfogadva830ms23856 KiB
117Elfogadva949ms23820 KiB
118Elfogadva777ms23820 KiB
119Elfogadva1.029s23860 KiB
120Elfogadva771ms23860 KiB
121Hibás válasz1.6s21556 KiB
122Hibás válasz1.567s21556 KiB
subtask90/15
123Elfogadva1ms316 KiB
124Hibás válasz1.575s21556 KiB
125Időlimit túllépés2.081s22336 KiB
126Időlimit túllépés2.081s12904 KiB
127Időlimit túllépés2.082s14132 KiB
128Időlimit túllépés2.082s22068 KiB
129Időlimit túllépés2.085s18740 KiB
130Elfogadva263ms20548 KiB
131Elfogadva2ms564 KiB
132Elfogadva2ms564 KiB
133Elfogadva2ms748 KiB
134Elfogadva2ms564 KiB
135Elfogadva2ms564 KiB
136Elfogadva2ms660 KiB
137Elfogadva2ms540 KiB
138Elfogadva2ms388 KiB
139Elfogadva2ms564 KiB
140Elfogadva85ms14404 KiB
141Elfogadva82ms14408 KiB
142Elfogadva82ms14504 KiB
143Elfogadva85ms14524 KiB
144Elfogadva82ms14388 KiB
145Elfogadva85ms14388 KiB
146Elfogadva114ms12004 KiB
147Elfogadva115ms12088 KiB
148Elfogadva112ms10600 KiB
149Elfogadva119ms17216 KiB
150Elfogadva467ms4652 KiB
151Elfogadva495ms4404 KiB
152Elfogadva354ms4404 KiB
153Elfogadva352ms4540 KiB
154Hibás válasz657ms6196 KiB
155Hibás válasz698ms6476 KiB
156Hibás válasz647ms6452 KiB
157Hibás válasz685ms6280 KiB
158Elfogadva474ms4404 KiB
159Elfogadva460ms4404 KiB
160Elfogadva453ms4512 KiB
161Elfogadva442ms4400 KiB
162Elfogadva1.243s23720 KiB
163Elfogadva1.212s23732 KiB
164Elfogadva1.225s23776 KiB
165Elfogadva1.023s23844 KiB
166Elfogadva718ms23812 KiB
167Elfogadva1.062s23744 KiB
168Elfogadva257ms16380 KiB
169Elfogadva263ms15924 KiB
170Elfogadva261ms14644 KiB
171Elfogadva254ms16964 KiB
172Elfogadva1.185s21144 KiB
173Hibás válasz1.233s21408 KiB
174Hibás válasz1.161s21156 KiB
175Hibás válasz1.129s21416 KiB
176Elfogadva1.264s21360 KiB
177Hibás válasz1.189s21156 KiB
178Elfogadva344ms16332 KiB
179Elfogadva352ms15168 KiB
180Elfogadva349ms14640 KiB
181Elfogadva340ms18996 KiB
182Hibás válasz1.876s21568 KiB
183Hibás válasz1.646s21556 KiB
184Hibás válasz1.671s21556 KiB
185Hibás válasz1.761s21556 KiB
186Hibás válasz1.677s21556 KiB
187Hibás válasz1.597s21520 KiB
188Elfogadva1.044s23864 KiB
189Elfogadva830ms23856 KiB
190Elfogadva949ms23820 KiB
191Elfogadva777ms23820 KiB
192Elfogadva1.029s23860 KiB
193Elfogadva771ms23860 KiB
194Hibás válasz1.6s21556 KiB
195Hibás válasz1.567s21556 KiB
196Időlimit túllépés2.079s15156 KiB
197Időlimit túllépés2.079s15412 KiB
198Időlimit túllépés2.079s14992 KiB
199Időlimit túllépés2.079s13876 KiB
200Időlimit túllépés2.095s13888 KiB
201Időlimit túllépés2.095s13492 KiB
202Időlimit túllépés2.095s13136 KiB
203Időlimit túllépés2.095s13328 KiB
204Időlimit túllépés2.075s12872 KiB
205Időlimit túllépés2.075s12836 KiB