167582025-05-12 10:42:14szilSiklóernyőzéscpp17Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1.697s21556 KiB
subtask20/5
3Időlimit túllépés2.091s22348 KiB
4Időlimit túllépés2.091s12852 KiB
5Időlimit túllépés2.091s14132 KiB
6Időlimit túllépés2.092s22068 KiB
7Időlimit túllépés2.078s18952 KiB
8Elfogadva268ms20532 KiB
subtask313/13
9Elfogadva2ms756 KiB
10Elfogadva2ms756 KiB
11Elfogadva2ms564 KiB
12Elfogadva2ms564 KiB
13Elfogadva2ms564 KiB
14Elfogadva2ms564 KiB
15Elfogadva2ms564 KiB
16Elfogadva2ms568 KiB
17Elfogadva2ms564 KiB
subtask410/10
18Elfogadva2ms756 KiB
19Elfogadva2ms756 KiB
20Elfogadva2ms564 KiB
21Elfogadva2ms564 KiB
22Elfogadva2ms564 KiB
23Elfogadva2ms564 KiB
24Elfogadva2ms564 KiB
25Elfogadva2ms568 KiB
26Elfogadva2ms564 KiB
27Elfogadva85ms14628 KiB
28Elfogadva82ms14512 KiB
29Elfogadva82ms14388 KiB
30Elfogadva86ms14384 KiB
31Elfogadva86ms14396 KiB
32Elfogadva82ms14388 KiB
33Elfogadva116ms12084 KiB
34Elfogadva123ms12084 KiB
35Elfogadva118ms10548 KiB
36Elfogadva123ms17204 KiB
subtask515/15
37Elfogadva2ms756 KiB
38Elfogadva2ms756 KiB
39Elfogadva2ms564 KiB
40Elfogadva2ms564 KiB
41Elfogadva2ms564 KiB
42Elfogadva2ms564 KiB
43Elfogadva2ms564 KiB
44Elfogadva2ms568 KiB
45Elfogadva2ms564 KiB
46Elfogadva495ms4660 KiB
47Elfogadva527ms4500 KiB
48Elfogadva370ms4536 KiB
49Elfogadva370ms4404 KiB
50Elfogadva699ms6568 KiB
51Elfogadva746ms6196 KiB
52Elfogadva690ms6196 KiB
53Elfogadva732ms6276 KiB
54Elfogadva497ms4404 KiB
55Elfogadva486ms4404 KiB
56Elfogadva477ms4408 KiB
57Elfogadva467ms4404 KiB
subtask610/10
58Elfogadva1.253s23860 KiB
59Elfogadva1.222s23908 KiB
60Elfogadva1.238s23824 KiB
61Elfogadva1.037s23920 KiB
62Elfogadva744ms23704 KiB
63Elfogadva1.062s23860 KiB
64Elfogadva263ms16500 KiB
65Elfogadva263ms15892 KiB
66Elfogadva257ms14648 KiB
67Elfogadva256ms17112 KiB
subtask711/11
68Elfogadva2ms756 KiB
69Elfogadva2ms756 KiB
70Elfogadva2ms564 KiB
71Elfogadva2ms564 KiB
72Elfogadva2ms564 KiB
73Elfogadva2ms564 KiB
74Elfogadva2ms564 KiB
75Elfogadva2ms568 KiB
76Elfogadva2ms564 KiB
77Elfogadva85ms14628 KiB
78Elfogadva82ms14512 KiB
79Elfogadva82ms14388 KiB
80Elfogadva86ms14384 KiB
81Elfogadva86ms14396 KiB
82Elfogadva82ms14388 KiB
83Elfogadva116ms12084 KiB
84Elfogadva123ms12084 KiB
85Elfogadva118ms10548 KiB
86Elfogadva123ms17204 KiB
87Elfogadva1.253s23860 KiB
88Elfogadva1.222s23908 KiB
89Elfogadva1.238s23824 KiB
90Elfogadva1.037s23920 KiB
91Elfogadva744ms23704 KiB
92Elfogadva1.062s23860 KiB
93Elfogadva263ms16500 KiB
94Elfogadva263ms15892 KiB
95Elfogadva257ms14648 KiB
96Elfogadva256ms17112 KiB
97Elfogadva1.208s21260 KiB
98Elfogadva1.259s21300 KiB
99Elfogadva1.192s21556 KiB
100Elfogadva1.156s21240 KiB
101Elfogadva1.292s21300 KiB
102Elfogadva1.213s21376 KiB
103Elfogadva354ms16440 KiB
104Elfogadva363ms15288 KiB
105Elfogadva358ms14584 KiB
106Elfogadva351ms18996 KiB
subtask821/21
107Elfogadva1ms316 KiB
108Elfogadva1.684s21556 KiB
109Elfogadva1.996s21556 KiB
110Elfogadva1.718s21452 KiB
111Elfogadva1.827s21576 KiB
112Elfogadva1.883s21556 KiB
113Elfogadva1.828s21556 KiB
114Elfogadva1.779s21556 KiB
115Elfogadva1.059s23888 KiB
116Elfogadva842ms23892 KiB
117Elfogadva970ms23860 KiB
118Elfogadva810ms23860 KiB
119Elfogadva1.029s23860 KiB
120Elfogadva795ms23860 KiB
121Elfogadva1.728s21556 KiB
122Elfogadva1.715s21556 KiB
subtask90/15
123Elfogadva1ms316 KiB
124Elfogadva1.684s21556 KiB
125Időlimit túllépés2.091s22348 KiB
126Időlimit túllépés2.091s12852 KiB
127Időlimit túllépés2.091s14132 KiB
128Időlimit túllépés2.092s22068 KiB
129Időlimit túllépés2.078s18952 KiB
130Elfogadva268ms20532 KiB
131Elfogadva2ms756 KiB
132Elfogadva2ms756 KiB
133Elfogadva2ms564 KiB
134Elfogadva2ms564 KiB
135Elfogadva2ms564 KiB
136Elfogadva2ms564 KiB
137Elfogadva2ms564 KiB
138Elfogadva2ms568 KiB
139Elfogadva2ms564 KiB
140Elfogadva85ms14628 KiB
141Elfogadva82ms14512 KiB
142Elfogadva82ms14388 KiB
143Elfogadva86ms14384 KiB
144Elfogadva86ms14396 KiB
145Elfogadva82ms14388 KiB
146Elfogadva116ms12084 KiB
147Elfogadva123ms12084 KiB
148Elfogadva118ms10548 KiB
149Elfogadva123ms17204 KiB
150Elfogadva495ms4660 KiB
151Elfogadva527ms4500 KiB
152Elfogadva370ms4536 KiB
153Elfogadva370ms4404 KiB
154Elfogadva699ms6568 KiB
155Elfogadva746ms6196 KiB
156Elfogadva690ms6196 KiB
157Elfogadva732ms6276 KiB
158Elfogadva497ms4404 KiB
159Elfogadva486ms4404 KiB
160Elfogadva477ms4408 KiB
161Elfogadva467ms4404 KiB
162Elfogadva1.253s23860 KiB
163Elfogadva1.222s23908 KiB
164Elfogadva1.238s23824 KiB
165Elfogadva1.037s23920 KiB
166Elfogadva744ms23704 KiB
167Elfogadva1.062s23860 KiB
168Elfogadva263ms16500 KiB
169Elfogadva263ms15892 KiB
170Elfogadva257ms14648 KiB
171Elfogadva256ms17112 KiB
172Elfogadva1.208s21260 KiB
173Elfogadva1.259s21300 KiB
174Elfogadva1.192s21556 KiB
175Elfogadva1.156s21240 KiB
176Elfogadva1.292s21300 KiB
177Elfogadva1.213s21376 KiB
178Elfogadva354ms16440 KiB
179Elfogadva363ms15288 KiB
180Elfogadva358ms14584 KiB
181Elfogadva351ms18996 KiB
182Elfogadva1.996s21556 KiB
183Elfogadva1.718s21452 KiB
184Elfogadva1.827s21576 KiB
185Elfogadva1.883s21556 KiB
186Elfogadva1.828s21556 KiB
187Elfogadva1.779s21556 KiB
188Elfogadva1.059s23888 KiB
189Elfogadva842ms23892 KiB
190Elfogadva970ms23860 KiB
191Elfogadva810ms23860 KiB
192Elfogadva1.029s23860 KiB
193Elfogadva795ms23860 KiB
194Elfogadva1.728s21556 KiB
195Elfogadva1.715s21556 KiB
196Időlimit túllépés2.091s15156 KiB
197Időlimit túllépés2.091s15156 KiB
198Időlimit túllépés2.091s15024 KiB
199Időlimit túllépés2.091s13800 KiB
200Időlimit túllépés2.082s13652 KiB
201Időlimit túllépés2.082s13620 KiB
202Időlimit túllépés2.082s13112 KiB
203Időlimit túllépés2.084s13108 KiB
204Időlimit túllépés2.079s12852 KiB
205Időlimit túllépés2.079s12992 KiB