167572025-05-12 10:30:05szilSiklóernyőzéscpp17Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms508 KiB
2Wrong answer1.565s21600 KiB
subtask20/5
3Time limit exceeded2.081s22336 KiB
4Time limit exceeded2.081s12904 KiB
5Time limit exceeded2.082s14132 KiB
6Time limit exceeded2.082s22068 KiB
7Time limit exceeded2.085s18740 KiB
8Accepted263ms20548 KiB
subtask313/13
9Accepted2ms564 KiB
10Accepted2ms564 KiB
11Accepted2ms748 KiB
12Accepted2ms564 KiB
13Accepted2ms564 KiB
14Accepted2ms660 KiB
15Accepted2ms540 KiB
16Accepted2ms388 KiB
17Accepted2ms564 KiB
subtask410/10
18Accepted2ms564 KiB
19Accepted2ms564 KiB
20Accepted2ms748 KiB
21Accepted2ms564 KiB
22Accepted2ms564 KiB
23Accepted2ms660 KiB
24Accepted2ms540 KiB
25Accepted2ms388 KiB
26Accepted2ms564 KiB
27Accepted85ms14404 KiB
28Accepted82ms14408 KiB
29Accepted82ms14504 KiB
30Accepted85ms14524 KiB
31Accepted82ms14388 KiB
32Accepted85ms14388 KiB
33Accepted114ms12004 KiB
34Accepted115ms12088 KiB
35Accepted112ms10600 KiB
36Accepted119ms17216 KiB
subtask50/15
37Accepted2ms564 KiB
38Accepted2ms564 KiB
39Accepted2ms748 KiB
40Accepted2ms564 KiB
41Accepted2ms564 KiB
42Accepted2ms660 KiB
43Accepted2ms540 KiB
44Accepted2ms388 KiB
45Accepted2ms564 KiB
46Accepted467ms4652 KiB
47Accepted495ms4404 KiB
48Accepted354ms4404 KiB
49Accepted352ms4540 KiB
50Wrong answer657ms6196 KiB
51Wrong answer698ms6476 KiB
52Wrong answer647ms6452 KiB
53Wrong answer685ms6280 KiB
54Accepted474ms4404 KiB
55Accepted460ms4404 KiB
56Accepted453ms4512 KiB
57Accepted442ms4400 KiB
subtask610/10
58Accepted1.243s23720 KiB
59Accepted1.212s23732 KiB
60Accepted1.225s23776 KiB
61Accepted1.023s23844 KiB
62Accepted718ms23812 KiB
63Accepted1.062s23744 KiB
64Accepted257ms16380 KiB
65Accepted263ms15924 KiB
66Accepted261ms14644 KiB
67Accepted254ms16964 KiB
subtask70/11
68Accepted2ms564 KiB
69Accepted2ms564 KiB
70Accepted2ms748 KiB
71Accepted2ms564 KiB
72Accepted2ms564 KiB
73Accepted2ms660 KiB
74Accepted2ms540 KiB
75Accepted2ms388 KiB
76Accepted2ms564 KiB
77Accepted85ms14404 KiB
78Accepted82ms14408 KiB
79Accepted82ms14504 KiB
80Accepted85ms14524 KiB
81Accepted82ms14388 KiB
82Accepted85ms14388 KiB
83Accepted114ms12004 KiB
84Accepted115ms12088 KiB
85Accepted112ms10600 KiB
86Accepted119ms17216 KiB
87Accepted1.243s23720 KiB
88Accepted1.212s23732 KiB
89Accepted1.225s23776 KiB
90Accepted1.023s23844 KiB
91Accepted718ms23812 KiB
92Accepted1.062s23744 KiB
93Accepted257ms16380 KiB
94Accepted263ms15924 KiB
95Accepted261ms14644 KiB
96Accepted254ms16964 KiB
97Accepted1.185s21144 KiB
98Wrong answer1.233s21408 KiB
99Wrong answer1.161s21156 KiB
100Wrong answer1.129s21416 KiB
101Accepted1.264s21360 KiB
102Wrong answer1.189s21156 KiB
103Accepted344ms16332 KiB
104Accepted352ms15168 KiB
105Accepted349ms14640 KiB
106Accepted340ms18996 KiB
subtask80/21
107Accepted1ms316 KiB
108Wrong answer1.575s21556 KiB
109Wrong answer1.876s21568 KiB
110Wrong answer1.646s21556 KiB
111Wrong answer1.671s21556 KiB
112Wrong answer1.761s21556 KiB
113Wrong answer1.677s21556 KiB
114Wrong answer1.597s21520 KiB
115Accepted1.044s23864 KiB
116Accepted830ms23856 KiB
117Accepted949ms23820 KiB
118Accepted777ms23820 KiB
119Accepted1.029s23860 KiB
120Accepted771ms23860 KiB
121Wrong answer1.6s21556 KiB
122Wrong answer1.567s21556 KiB
subtask90/15
123Accepted1ms316 KiB
124Wrong answer1.575s21556 KiB
125Time limit exceeded2.081s22336 KiB
126Time limit exceeded2.081s12904 KiB
127Time limit exceeded2.082s14132 KiB
128Time limit exceeded2.082s22068 KiB
129Time limit exceeded2.085s18740 KiB
130Accepted263ms20548 KiB
131Accepted2ms564 KiB
132Accepted2ms564 KiB
133Accepted2ms748 KiB
134Accepted2ms564 KiB
135Accepted2ms564 KiB
136Accepted2ms660 KiB
137Accepted2ms540 KiB
138Accepted2ms388 KiB
139Accepted2ms564 KiB
140Accepted85ms14404 KiB
141Accepted82ms14408 KiB
142Accepted82ms14504 KiB
143Accepted85ms14524 KiB
144Accepted82ms14388 KiB
145Accepted85ms14388 KiB
146Accepted114ms12004 KiB
147Accepted115ms12088 KiB
148Accepted112ms10600 KiB
149Accepted119ms17216 KiB
150Accepted467ms4652 KiB
151Accepted495ms4404 KiB
152Accepted354ms4404 KiB
153Accepted352ms4540 KiB
154Wrong answer657ms6196 KiB
155Wrong answer698ms6476 KiB
156Wrong answer647ms6452 KiB
157Wrong answer685ms6280 KiB
158Accepted474ms4404 KiB
159Accepted460ms4404 KiB
160Accepted453ms4512 KiB
161Accepted442ms4400 KiB
162Accepted1.243s23720 KiB
163Accepted1.212s23732 KiB
164Accepted1.225s23776 KiB
165Accepted1.023s23844 KiB
166Accepted718ms23812 KiB
167Accepted1.062s23744 KiB
168Accepted257ms16380 KiB
169Accepted263ms15924 KiB
170Accepted261ms14644 KiB
171Accepted254ms16964 KiB
172Accepted1.185s21144 KiB
173Wrong answer1.233s21408 KiB
174Wrong answer1.161s21156 KiB
175Wrong answer1.129s21416 KiB
176Accepted1.264s21360 KiB
177Wrong answer1.189s21156 KiB
178Accepted344ms16332 KiB
179Accepted352ms15168 KiB
180Accepted349ms14640 KiB
181Accepted340ms18996 KiB
182Wrong answer1.876s21568 KiB
183Wrong answer1.646s21556 KiB
184Wrong answer1.671s21556 KiB
185Wrong answer1.761s21556 KiB
186Wrong answer1.677s21556 KiB
187Wrong answer1.597s21520 KiB
188Accepted1.044s23864 KiB
189Accepted830ms23856 KiB
190Accepted949ms23820 KiB
191Accepted777ms23820 KiB
192Accepted1.029s23860 KiB
193Accepted771ms23860 KiB
194Wrong answer1.6s21556 KiB
195Wrong answer1.567s21556 KiB
196Time limit exceeded2.079s15156 KiB
197Time limit exceeded2.079s15412 KiB
198Time limit exceeded2.079s14992 KiB
199Time limit exceeded2.079s13876 KiB
200Time limit exceeded2.095s13888 KiB
201Time limit exceeded2.095s13492 KiB
202Time limit exceeded2.095s13136 KiB
203Time limit exceeded2.095s13328 KiB
204Time limit exceeded2.075s12872 KiB
205Time limit exceeded2.075s12836 KiB